Linear Time Online Algorithms for Constructing Linear-size Suffix Trie

Diptarama Hendrian, Takuya Takagi, Shunsuke Inenaga +2

The suffix trees are fundamental data structures for various kinds of string processing. The suffix tree of a text string $T$ of length $n$ has $O(n)$ nodes and edges, and the stri…