2002 · 452 citations · 5 references
ComputingComputer ScienceMathematicsAlgorithmsData StructuresTheory Of ComputationComputational ComplexitySorting AlgorithmsString AlgorithmsAlphabetsComplexity Of String AlgorithmsLower BoundsLower Bounds For SortingString SearchString SortingTime Comparison
The suffix tree of a string is the fundamental data structure of combinatorial pattern matching. Weiner (1973), who introduced the data structure, gave an O(n)-time algorithm for building the suffix tree of an n-character string drawn from a constant size alphabet. In the comparison model, there is a trivial /spl Omega/(n log n)-time lower bound based on sorting, and Weiner's algorithm matches this bound trivially. For integer alphabets, a substantial gap remains between the known upper and lower bounds, and closing this gap is the main open question in the construction of suffix trees. There is no super-linear lower bound, and the fastest known algorithm was the O(n log n) time comparison based algorithm. We settle this open problem by closing the gap: we build suffix trees in linear time for integer alphabet.
5
Linear pattern matching algorithms
Peter Weiner · 1973 · 1.8K citations
A Space-Economical Suffix Tree Construction Algorithm
Edward M. McCreight · Journal of the ACM · 1976 · 1.5K citations · Full text
Fast Algorithms for Finding Nearest Common Ancestors
Dov Harel, Robert E. Tarjan · SIAM Journal on Computing · 1984 · 1.1K citations