Ukkonen's algorithm

In computer science, Ukkonen's algorithm is a linear-time, online algorithm for constructing suffix trees, proposed by Esko Ukkonen in 1995.^[1]

The algorithm begins with an implicit suffix tree containing the first character of the string. Then it steps through the string adding successive characters until the tree is complete. This order addition of characters gives Ukkonen's algorithm its "on-line" property. Earlier algorithms proceeded backward from the last character to the first one, let it be from the longest to the shortest suffix ^[2] or from the shortest to the longest suffix.^[3] The naive implementation for generating a suffix tree requires O(n²) or even O(n³) time, where n is the length of the string. By exploiting a number of algorithmic techniques, Ukkonen reduced this to O(n) (linear) time, for constant-size alphabets, and O(n log n) in general.

References

^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1007/BF01206331, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1007/BF01206331 instead.
^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1145/321941.321946, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1145/321941.321946 instead.
^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1109/SWAT.1973.13, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1109/SWAT.1973.13 instead.

External links

Original Ukkonen's paper PDF | PDF with figures
McCreight's paper in PDF
Weiner's paper in PDF
Detailed explanation in plain English
Fast String Searching With Suffix Trees Mark Nelson's tutorial. Has an implementation example written with C++.
Implementation in Java
Implementation in C#
Implementation in C with detailed explanation
Lecture slides by Guy Blelloch
Ukkonen's homepage
Text-Indexing project (Ukkonen's linear-time construction of suffix trees)
Implementation in C Part 1 Part 2 Part 3 Part 4 Part 5 Part 6

This computer science article is a stub. You can help Wikipedia by expanding it.

[1] Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1007/BF01206331, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1007/BF01206331 instead.

[2] Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1145/321941.321946, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1145/321941.321946 instead.

[3] Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1109/SWAT.1973.13, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1109/SWAT.1973.13 instead.

[1]

[2]

[3]