Suffix Tree

The compressed trie of all suffixes of a string. Every substring corresponds to a path from the root, so a huge family of questions becomes tree navigation.

Structure

• $n$ leaves (one per suffix, with a sentinel $ to prevent a suffix being a prefix of another) and at most $n-1$ internal nodes.
• Edges are labelled with substrings, stored as index pairs (l, r) into the original string — so the whole tree is $O(n)$ space despite representing $O(n^2)$ substrings.
• Every internal node has $\ge 2$ children.

s = banana$

            root
         /   |    \
    banana$  a      na
            / \    /  \
          $  na   $   na$
              |
             ...

What it answers

Question	Method	Cost
Is $t$ a substring?	walk from the root	$O(|t|)$
Number of occurrences of $t$	leaves under the arrival node	$O(|t|)$
All occurrence positions	traverse that subtree	$O(|t|+\text{output})$
Longest repeated substring	deepest internal node	$O(n)$
Number of distinct substrings	sum of edge lengths	$O(n)$
Longest common substring of two strings	generalised tree; deepest node with leaves from both	$O(n)$
Longest palindromic substring	generalised tree of $s$ and $\mathrm{reverse}(s)$ + LCA	$O(n)$
All maximal repeats	internal nodes with left-diverse children	$O(n)$
Longest common extension	LCA of two leaves	$O(1)$ after preprocessing
Matching statistics	one downward walk with suffix links	$O(m)$

Construction

Algorithm	Direction	Online	Difficulty
Weiner (1973)	right to left	prepend	$O(n\sigma )$ memory
McCreight (1976)	longest to shortest suffix	no	hard
Ukkonen (1995)	left to right	yes	hard, most taught
Farach (1997)	divide and conquer	no	theoretical
From a suffix array + LCP	—	no	easy — see below

Do not implement a suffix tree

In a contest, use one of:

• Suffix automaton — 30 lines, online, and its link tree is the suffix tree of the reversed string;
• Suffix array + LCP — less memory, and the “LCP interval tree” gives suffix-tree navigation.

Ukkonen’s algorithm is famously easy to get subtly wrong, and there is essentially no problem that requires it.

Building it from a suffix array

The suffix tree’s internal nodes correspond exactly to LCP intervals: maximal ranges of the suffix array whose minimum LCP equals the node’s string depth. A monotonic stack over the LCP array constructs this tree in $O(n)$:

// classic stack-based construction of the "LCP interval tree"
for (int i = 1; i <= n; i++) {
    int cur = i - 1;
    while (!st.empty() && lcp[st.top()] > lcp[i]) { /* close a node */ cur = st.top(); st.pop(); }
    if (!st.empty() && lcp[st.top()] == lcp[i]) { /* attach to the existing node */ }
    st.push(i);
}

This gives you suffix-tree structure with suffix-array memory — the practical best of both.

The three suffix structures compared

	Suffix tree	Suffix array	Suffix automaton
Nodes	$\le 2n$	$n$ integers	$\le 2n$
Memory constant	high ($\sigma$ per node)	lowest	medium
Build difficulty	hardest	easy at $O(n{\log }^{2}n)$	easiest
Online	Ukkonen only	no	yes
Lexicographic order	✔	✔ natural	needs work
All substrings	✔	via LCP intervals	✔ natural

Generalised suffix tree

For a set of strings, concatenate them with distinct separators, or build the automaton with resets. Each leaf records which string it came from; a node containing leaves from every input is a common substring. This is how “longest common substring of $k$ strings” is solved in linear time.

See also: Suffix Automaton · Suffix Array · Ukkonen