Ukkonen's algorithm

Ukkonen proposed a linear time algorithm for building Suffix trees.

Ukkonen's 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 it's "on-line" property; earlier algorithms proceeded backward from the last character. The naive implementation of this algorithm requires O(n^2) or even O(n^3) time, however applying several programming tricks reduces this to O(n) time.

See also

• Suffix tree

References

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