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 linearsize suffix tries (LSTs), proposed by Crochemore et al. [Linearsize suffix tries, TCS 638:171178, 2016], are a "standalone" 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 "directly" 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 righttoleft construction algorithm works in O(n log sigma) time and O(n) space and the lefttoright 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.
BibTeX  Entry
@InProceedings{hendrian_et_al:LIPIcs:2019:10501,
author = {Diptarama Hendrian and Takuya Takagi and Shunsuke Inenaga},
title = {{Online Algorithms for Constructing LinearSize Suffix Trie}},
booktitle = {30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)},
pages = {30:130:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771030},
ISSN = {18688969},
year = {2019},
volume = {128},
editor = {Nadia Pisanti and Solon P. Pissis},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10501},
URN = {urn:nbn:de:0030drops105016},
doi = {10.4230/LIPIcs.CPM.2019.30},
annote = {Keywords: Indexing structure, Linearsize suffix trie, Online algorithm, Pattern Matching}
}
Keywords: 

Indexing structure, Linearsize suffix trie, Online algorithm, Pattern Matching 
Collection: 

30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019) 
Issue Date: 

2019 
Date of publication: 

06.06.2019 