Name
Abstract | ||
|---|---|---|
The suffix trees are fundamental data structures for various kinds of string processing. The suffix tree of a string $T$ of length $n$ has $O(n)$ nodes and edges, and the string label of each edge is encoded by a pair of positions in $T$. Thus, even after the tree is built, the input text $T$ needs to be kept stored and random access to $T$ is still needed. The linear-size suffix tries (LSTs), proposed by Crochemore et al. [Linear-size suffix tries, TCS 638:171-178, 2016], are a `stand-aloneu0027 alternative to the suffix trees. Namely, the LST of a string $T$ of length $n$ occupies $O(n)$ total space, and supports pattern matching and other tasks in the same efficiency as the suffix tree without the need to store the input text $T$. Crochemore et al. proposed an offline algorithm which transforms the suffix tree of $T$ into the LST of $T$ in $O(n log sigma)$ time and $O(n)$ space, where $sigma$ is the alphabet size. In this paper, we present two types of online algorithms which `directlyu0027 construct the LST, from right to left, and from left to right, without constructing the suffix tree as an intermediate structure. Both algorithms construct the LST incrementally when a new symbol is read, and do not access to the previously read symbols. The right-to-left construction algorithm works in $O(n log sigma)$ time and $O(n)$ space and the left-to-right construction algorithm works in $O(n (log sigma + log n / log log n))$ time and $O(n)$ space. The main feature of our algorithms is that the input text does not need to be stored. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.4230/LIPIcs.CPM.2019.30 | Combinatorial Pattern Matching |
Field | DocType | Volume |
Binary logarithm,Online algorithm,Discrete mathematics,Data structure,Combinatorics,Suffix,Suffix tree,Pattern matching,Trie,Mathematics,Random access | Journal | abs/1901.10045 |
Citations | PageRank | References |
0 | 0.34 | 12 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Diptarama Hendrian | 1 | 0 | 1.01 |
| Takuya Takagi | 2 | 11 | 6.97 |
| Shunsuke Inenaga | 3 | 595 | 79.02 |