Ukkonen's Algorithm

Ukkonen's algorithm is a linear time, online algorithm for constructing suffix trees, proposed by Esko Ukkonen in 1995. It begins with an implicit suffix tree containing only the first character of the string, then steps through the remaining characters one at a time, extending the tree as it goes, which gives the algorithm its online property since it never needs to see the whole string in advance. Earlier suffix tree construction algorithms by Peter Weiner in 1973 and Edward M. McCreight in 1976 built the tree by working backward from the last character or from the longest suffix to the shortest, rather than processing the string in the forward, online order Ukkonen's method allows.