McCreight's Algorithm

Purpose: Build a suffix tree in $O(n)$ time (constant alphabet), inserting suffixes from longest to shortest. Published in 1976, seven years before Ukkonen’s, and considerably easier to follow.

Algorithm

Insert suffixes $S_0,S_1,\dots ,S_{n-1}$ in order of decreasing length. Naively each insertion walks from the root, giving $O(n^2)$. Two devices make it linear:

1. Suffix links. After inserting the suffix starting at $i$, the node for $x\alpha$ links to the node for $\alpha$. To insert suffix $i+1$, follow the suffix link from the parent of the last inserted leaf instead of restarting at the root.
2. Skip/count. When descending a known path, do not compare characters one by one — read the edge length and jump, comparing only the first character of each edge. The path length is known in advance, so this is $O(\text{number of edges})$ rather than $O(\text{characters})$.

The head (longest prefix of the current suffix already in the tree) and tail (the rest) decomposition is McCreight’s central bookkeeping: ${\mathrm{head}}_{i+1}$ is always at least $|{\mathrm{head}}_i|-1$, which is what bounds the total work.

Complexity

• Time: $O(n)$ amortized for a constant alphabet; $O(n\log \sigma )$ with balanced-tree children
• Space: $O(n)$ nodes

Why the amortization works

$|{\mathrm{head}}_i|$ decreases by at most 1 per insertion and can only increase by the characters actually consumed. Summing over all $n$ insertions, the total descent is $O(n)$ — the same telescoping argument that makes Kasai’s LCP construction linear.

McCreight vs Ukkonen vs Weiner

	Direction	Online?	Notes
Weiner (1973)	right to left	prepends characters	the original; memory-hungry, “algorithm of the year 1973”
McCreight (1976)	longest to shortest suffix	offline	cleaner, less memory
Ukkonen (1995)	left to right	online — the key advantage	most commonly taught
Farach (1997)	divide and conquer	offline	linear for integer alphabets

All four build the same tree in $O(n)$. Ukkonen wins on online construction (you can feed characters as they arrive), which matters for streaming and for generalised suffix trees built incrementally.

In a contest

Do not write any of them. A suffix automaton is ~30 lines and covers nearly every suffix-tree application; a suffix array with LCP covers the rest with less memory.

Variants / Use Cases

• Generalised suffix trees — multiple strings with distinct terminators, for longest common substring of $k$ strings
• Matching statistics — the byproduct McCreight’s head/tail computation naturally produces
• Suffix Tree — the topic page listing what the structure answers
• Ukkonen — the online alternative