Abstract.
We review the linear-time suffix tree constructions by Weiner, McCreight, and Ukkonen. We use the terminology of the most recent algorithm, Ukkonen's on-line construction, to explain its historic predecessors. This reveals relationships much closer than one would expect, since the three algorithms are based on rather different intuitive ideas. Moreover, it completely explains the differences between these algorithms in terms of simplicity, efficiency, and implementation complexity.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received February 12, 1995; revised January 28, 1996.
Rights and permissions
About this article
Cite this article
Giegerich, R., Kurtz, S. From Ukkonen to McCreight and Weiner: A Unifying View of Linear-Time Suffix Tree Construction . Algorithmica 19, 331–353 (1997). https://doi.org/10.1007/PL00009177
Issue Date:
DOI: https://doi.org/10.1007/PL00009177