Suffix Tree

data-structures computation

Definition

Suffix Tree

A suffix tree for a string $T$ is a compressed trie of all suffixes of T\$$, where $$ is a fresh letter marking the end of the string.

Each leaf stores the starting position of one suffix. The children at each node are ordered by the lexicographic order of their edge labels.

Query

Substring search

Given a suffix tree for $T$ and a pattern $P$, walk down from the root matching $P$ edge by edge.

Search(root, P):
    u = root
    i = 0                            // position in P
    while i < |P|:
        find child v of u whose edge label starts with P[i]
        if no such child:
            return null              // P does not occur in T
        L = label(u, v)
        k = min(|P| - i, |L|)
        if P[i..i+k-1] != L[0..k-1]:
            return null              // mismatch
        if i + k = |P|:
            return (v, k)            // P ends inside edge (u, v)
        u = v
        i = i + k
    return (u, 0)                     // P ends at node u

Runtime: $O(|P|)$ when the alphabet has constant size. Finding the correct child takes $O(1)$ per step with a direct lookup table at each node. With a general ordered alphabet, the children are ordered by lexicographic order, so a binary search over the children takes $O(\log |\Sigma |)$ per step, yielding $O(|P|\log |\Sigma |)$.

Finding all occurrences

Once the locus $(v,k)$ of $P$ is found, every leaf in the subtree rooted at $v$ corresponds to an occurrence of $P$ in $T$. Traverse the subtree and collect the leaf positions.

Runtime: $O(|P|+\text{occ})$ where $\text{occ}$ is the number of occurrences. The $|P|$ term comes from the search; the $\text{occ}$ term from traversing the subtree.

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$.