Ukkonen's algorithm

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

Additional recommended knowledge

How to quickly check pipettes?

Daily Sensitivity Test

What is the Correct Way to Check Repeatability in Balances?

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.

References

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