Ukkonen's Algorithm

Purpose: Build a suffix tree online, in $O(n)$ time for a constant alphabet (or $O(n\log \sigma )$ with maps), processing the string one character at a time.

Algorithm

The tree is built in $n$ phases; phase $i$ extends the implicit suffix tree of s[0..i) to s[0..i]. Naively each phase would insert all $i$ suffixes, giving $O(n^2)$. Three tricks bring it down to linear:

1. Edge-label compression. Store edges as index pairs (l, r) into the original string rather than as explicit substrings. Leaf edges use a shared “current end” variable, so extending every leaf is one increment — this is Rule 1 (leaf extension), handled implicitly.
2. Suffix links. Every internal node representing string $x\alpha$ has a link to the node representing $\alpha$. After inserting one suffix, follow the suffix link to reach the insertion point for the next one in $O(1)$ amortized, instead of walking down from the root.
3. Rule 3 stops the phase. If the character to insert is already present on the path, it will also be present for every shorter suffix, so the whole phase can stop early (“showstopper”). The remaining suffixes are handled implicitly and picked up in later phases.

The active point — a triple (active_node, active_edge, active_length) plus a remainder counter — encodes where the next insertion goes and is updated in $O(1)$ per step.

Complexity

• Time: $O(n)$ for a constant alphabet, $O(n\log \sigma )$ with map children, $O(n\sigma )$ memory with array children
• Space: $O(n)$ nodes ($\le 2n$)

Why It Works

The amortization is on the sum of active_length. It increases by at most 1 per phase (a total of $n$), and every suffix-link hop or explicit insertion decreases it. Since it never goes negative, the total work over all phases is $O(n)$. Rule 3 makes each phase stop after the first “already present” character, so the total number of explicit extensions across all phases is also $O(n)$.

It is genuinely fiddly

Ukkonen’s is famous for being hard to implement correctly from the paper — the edge cases around the active point and the remainder counter are where everyone loses an hour. In a contest, prefer a suffix automaton (about 30 lines, does most of the same jobs) or a suffix array + LCP.

What a suffix tree gives you

• Substring existence in $O(m)$
• Number of occurrences of a pattern — subtree leaf count
• Longest repeated substring — deepest internal node
• Longest common substring of $k$ strings — generalised suffix tree
• Longest palindromic substring — via generalised tree of $s$ and reverse($s$) + LCA
• All maximal repeats, tandem repeats

Variants / Use Cases

• McCreight — linear but offline (right-to-left), simpler in some ways
• Weiner — the original linear construction, builds right to left
• Farach — linear for integer alphabets, no $\sigma$ factor
• Suffix automaton — the suffix tree of the reversed string is the link tree of the automaton; usually the better contest tool
• Suffix array + LCP — same power, less memory, much easier to get right