Weiner's Algorithm

Purpose: The first linear-time suffix tree construction (1973). Donald Knuth called it “the algorithm of the year 1973.” It builds the tree by prepending characters — inserting suffixes from shortest to longest, i.e. processing the string right to left.

Algorithm

Process the string from the last character backwards. At each step, the tree contains all suffixes of the current suffix of $S$, and one more suffix is added by prepending a character.

Two auxiliary tables per node $v$ and character $c$:

• link vector $I_v[c]$ — a boolean: does $cv$ occur as a substring?
• indicator vector $A_v[c]$ — a pointer: the node for $cv$, if that node exists.

These are exactly the reverse of Ukkonen’s and McCreight’s suffix links: they answer “where does prepending $c$ take me?” rather than “where does dropping the first character take me?”

Insertion walks up from the previously inserted leaf using $I$ and $A$ until it finds where the new suffix branches off, then splits an edge and adds a leaf.

Complexity

• Time: $O(n)$ for a constant alphabet
• Space: $O(n\sigma )$ for the two tables — this is the problem. For $\sigma =256$ that is a 256× blowup versus McCreight.

Why it was superseded

The $O(n\sigma )$ tables made Weiner’s algorithm impractical for anything but tiny alphabets. McCreight (1976) achieved the same $O(n)$ time with $O(n)$ space by reversing the direction of construction, and Ukkonen (1995) added online construction. Weiner’s algorithm survives as a historical landmark and as the conceptual ancestor of the suffix automaton, whose suffix links point in the same “prepend” direction.

The connection worth knowing

Weiner’s prepend-based view is precisely the view a suffix automaton of the reversed string takes. Concretely:

The suffix link tree of the suffix automaton of $\mathrm{reverse}(S)$ is the suffix tree of $S$.

This is why the suffix automaton — 30 lines, online, $O(n\sigma )$ or $O(n\log \sigma )$ — is the modern practical answer to almost every suffix-tree problem. It is Weiner’s idea in a form that is easy to implement.

History of linear suffix structures

Year	Result
1973	Weiner — first linear suffix tree, $O(n\sigma )$ space
1976	McCreight — linear time, $O(n)$ space
1983	Blumer et al. — the DAWG / suffix automaton
1990	Manber-Myers — suffix arrays in $O(n\log n)$, far less memory
1995	Ukkonen — online linear construction
1997	Farach — linear for integer alphabets
2003	DC3 — simple linear suffix array
2009	SA-IS — fast linear suffix array, the current standard

Variants / Use Cases

• Suffix automaton — the practical modern descendant; use this
• Ukkonen — if you genuinely need an explicit suffix tree, built online
• Suffix Tree — what the structure is good for