Suffix Tree

Definition

Suffix Tree

A suffix tree stores all suffixes of a string in one compressed trie. For $T\in {\Sigma }^{\ast }$ of length $n$, append a fresh end marker \\notin\Sigma$andwrite$U=T$$. The stored strings are

$$\{U[i..n]:0\le i\le n\}.$$

Suffixes with the same beginning share a path. Chains without branching are compressed into single edges labelled by non-empty substrings of $U$; outgoing edges start with distinct characters. Reading the labels from the root to leaf $i$ spells exactly $U[i..n]$.

The leaf label $i$ is the suffix’s starting position, not its length. The unique end marker prevents any suffix from being a prefix of another, so all $n+1$ suffixes end at distinct leaves. Children may be arranged in lexicographic order, but this order is not required by the definition.

Query

For each non-empty pattern $P_i$ (without the end marker):

1. Follow the pattern from the root, comparing edge labels. A missing edge or mismatch means no occurrence. The pattern may end inside an edge.
2. Collect the shifts by DFS through the matching subtree. Each leaf stores a suffix-start index, and $P_i$ occurs exactly at suffixes beginning with $P_i$.

With constant-time child selection,

$$\underset{\text{match the path}}{\underbrace{O(|P_i|)}}+\underset{\text{report leaf indices}}{\underbrace{O({\mathrm{occ}}_T(P_i))}},$$

where ${\mathrm{occ}}_T(P_i)$ counts occurrences. The DFS bound follows because every internal node below the root branches. Reported shifts need not be sorted.

Space Encoding

Let $n=|T|$ and U=T\$$. The compressed tree has n+1$leavesand$O(n+1)$ vertices and edges.

• Leaf: store one suffix-start index.
• Edge: store two inclusive indices $(\ell ,r)$ representing $U[\ell ..r]$, rather than copying the substring.
• Text: store $U$ once; edge characters are read directly from it.

This uses $O(n+1)$ machine words with linear-space child storage. Explicitly copied edge labels can instead require $\Theta (n^2)$ space.

Construction Time

• Naïve: insert each suffix separately; their total length gives $O((n+1{)}^2)$ time.
• Linear: Weiner (1973), McCreight (1976), and Ukkonen (1995) achieve $O(n+1)$ time for a constant-size alphabet.

The tree is built once and reused for every pattern. A constant-size alphabet also permits the constant-time child selection assumed in the query bound; sorted child arrays for a general alphabet add an $O(\log (|\Sigma |+1))$ factor to path traversal.

Examples

Suffixes of $\text{banana}$

For $T=\text{banana}$, append the fresh letter \$$ and build the compressed trie of the suffixes of \text{banana}$$:

$$\begin{array}{rl}0& :\text{banana}\$\\ 1& :\text{anana}\$\\ 2& :\text{nana}\$\\ 3& :\text{ana}\$\\ 4& :\text{na}\$\\ 5& :\text{a}\$\\ 6& :\$\end{array}$$

The leaf labelled $3$ represents the suffix T[3..]\ = \text{ana}$$.

Substring lookup

A string $P$ occurs in $T$ iff $P$ labels a path starting at the root of the suffix tree.

For $T=\text{banana}$, the string $\text{ana}$ occurs because the path

$$\epsilon \stackrel{a}{\to }\text{a}\stackrel{na}{\to }\text{ana}$$

exists. The leaves below this path give the starting positions $1$ and $3$.