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

Correct Test Weight Handling Guide: 12 Practical Tips

How to ensure accurate weighing results every day?

Don't let static charges disrupt your weighing accuracy

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