Ukkonen's algorithm

From Wikipedia, the free encyclopedia

In 1995, Esko Ukkonen proposed a linear-time, online algorithm for constructing suffix trees that has come to be known as Ukkonen's algorithm.

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. The naive implementation of this algorithm requires O(n²) or even O(n³) time (see Big-O notation), where n is the number of characters in the string, but by exploiting a number of algorithmic techniques this can be reduced to O(n) (linear) time.

[edit] References

• E. Ukkonen. (1995). On-line construction of suffix trees. Algorithmica 14(3):249-260. PDF | PDF with figures

[edit] External links

• Fast String Searching With Suffix Trees Mark Nelson's excellent tutorial. Has an implementation example written with C++.