TY - GEN
T1 - Optimal logarithmic time randomized suffix tree construction
AU - Farach, Martin
AU - Muthukrishnant, S.
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1996.
PY - 1996
Y1 - 1996
N2 - The suffix tree of a string, the fundamental data structure in the area of combinatorial pattern matching, has many elegant applications. In this paper, we present a novel, simple sequential algorithm for the construction of suffix trees. We are also able to parallelize our algorithm so that we settle the main open problem in the construction of suffix trees: we give a Las Vegas CRCW PRAM algorithm that constructs the suffix tree of a binary string of length n in O(log n) time and O(n) work with high probability. In contrast, the previously known work-optimal algorithms, while deterministic, take Ω(log2 n) time. We also give a work-optimal randomized comparison-based algorithm to convert any string over an unbounded alphabet to an equivalent string over a binary alphabet. As a result, we obtain the first work-optimal algorithm for suffix tree construction under the unbounded alphabet assumption.
AB - The suffix tree of a string, the fundamental data structure in the area of combinatorial pattern matching, has many elegant applications. In this paper, we present a novel, simple sequential algorithm for the construction of suffix trees. We are also able to parallelize our algorithm so that we settle the main open problem in the construction of suffix trees: we give a Las Vegas CRCW PRAM algorithm that constructs the suffix tree of a binary string of length n in O(log n) time and O(n) work with high probability. In contrast, the previously known work-optimal algorithms, while deterministic, take Ω(log2 n) time. We also give a work-optimal randomized comparison-based algorithm to convert any string over an unbounded alphabet to an equivalent string over a binary alphabet. As a result, we obtain the first work-optimal algorithm for suffix tree construction under the unbounded alphabet assumption.
UR - http://www.scopus.com/inward/record.url?scp=84947716322&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84947716322&partnerID=8YFLogxK
U2 - 10.1007/3-540-61440-0_158
DO - 10.1007/3-540-61440-0_158
M3 - Conference contribution
AN - SCOPUS:84947716322
SN - 3540614400
SN - 9783540614401
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 550
EP - 561
BT - Automata, Languages and Programming - 23rd International Colloquium, ICALP 1996, Proceedings
A2 - Meyer auf der Heide, Friedhelm
A2 - Monien, Burkhard
PB - Springer Verlag
T2 - 23rd International Colloquium on Automata, Languages, and Programming, ICALP 1996
Y2 - 8 July 1996 through 12 July 1996
ER -