Optimal suffix tree construction with large alphabets
Top Cited Papers
- 22 November 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 137-143
- https://doi.org/10.1109/sfcs.1997.646102
Abstract
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.Keywords
This publication has 4 references indexed in Scilit:
- Efficient and Elegant Subword-Tree ConstructionPublished by Springer Nature ,1985
- Fast Algorithms for Finding Nearest Common AncestorsSIAM Journal on Computing, 1984
- A Space-Economical Suffix Tree Construction AlgorithmJournal of the ACM, 1976
- Linear pattern matching algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1973