Ukkonen's algorithm

The original algorithm presented by Peter Weiner proceeded backward from the last character to the first one from the shortest to the longest suffix.

Ukkonen's algorithm constructs an implicit suffix tree Ti for each prefix S[1...i] of S (S being the string of length n).

There are three extension rules: One important point to note is that from a given node (root or internal), there will be one and only one edge starting from one character.

The naive implementation for generating a suffix tree going forward requires O(n2) or even O(n3) time complexity in big O notation, where n is the length of the string.

To better illustrate how a suffix tree is constructed using Ukkonen's algorithm, we can consider the string S = xabxac.