Suffix Trees, Suffix Automata & Compressed Indexes

Compact Suffix Tries and Suffix Trees

A suffix trie for a terminated text $T=S\$$ stores every suffix of $T$. It answers substring queries by following the pattern from the root, but explicitly representing all suffix paths can require $\Theta(N^2)$ nodes. A suffix tree compresses each maximal nonbranching path into one edge labeled by an interval $[l,r)$ of the original text. Edge labels therefore occupy constant metadata rather than copied substrings, and the resulting tree has $O(N)$ explicit nodes and edges.

Explicit nodes are the root, branching nodes, and leaves; an implicit node is a position inside a compressed edge. Every leaf identifies one suffix start. For an internal node whose path label is $a\alpha$, its suffix link points to the node with path label $\alpha$, removing the first symbol. These links are the mechanism that lets online construction move between related suffixes without rescanning them.

A unique sentinel not present elsewhere ensures that every suffix ends at a distinct leaf and no suffix is a prefix of another. A generalized suffix tree indexes several texts by assigning each one a distinct sentinel, then annotating leaves with document identifiers. Queries remain $O(M)$ for a length-$M$ pattern when outgoing edges support constant expected-time or alphabet-indexed lookup; reporting $K$ occurrences adds $O(K)$.

Online Suffix-Tree Construction

Ukkonen’s algorithm processes $T$ left to right and maintains the suffix tree for every prefix. Its active point—(active_node, active_edge, active_length)—may denote either an explicit node or a position inside an edge. The remainder counts suffix extensions still pending in the current phase. All leaves share a mutable global end index, so extending every leaf costs $O(1)$ rather than touching them individually.

For the next symbol $c$, an extension has three outcomes:

1. If the active point ends at a leaf, its shared end already exposes $c$; this is the traditional Rule 1.
2. If no matching continuation exists, create a leaf or split an edge and attach a leaf. Link the previous split node to the current split node when appropriate.
3. If the next edge symbol already equals $c$, increment active_length and stop the phase early. The remaining suffixes are present implicitly; the remainder is not incremented again for this match.

After an explicit insertion, decrement the remainder and move the active point through a suffix link or, at the root, shorten the active length and advance the active edge. The skip/count trick descends whole edges using their lengths. Each phase may contain many extensions, but suffix links, shared leaf ends, early stopping, and skip/count make total construction $O(N)$ for a fixed or integer alphabet.

flowchart TD
    Start["Add T[i]; increment remainder"] --> Test{"Continuation by T[i] exists?"}
    Test -->|"Yes: Rule 3"| Extend["Increase active length; stop phase"]
    Test -->|"No"| Insert["Create leaf or split edge"]
    Insert --> Link["Resolve pending suffix link"]
    Link --> Dec["Decrement remainder"]
    Dec --> More{"Remainder nonzero?"}
    More -->|"No"| Next["Advance to next phase"]
    More -->|"Yes"| Move["Follow suffix link or adjust at root"]
    Move --> Skip["Skip/count to canonical active point"]
    Skip --> Test

Suffix Automata and End-Position Classes

A suffix automaton (SAM) is the minimal deterministic automaton of the substring language of $S$ when every reachable state is accepting; equivalently, with only suffix states marked accepting, the same transition graph recognizes the suffixes. Every substring labels a path from the initial state, allowing $\Theta(N^2)$ distinct substrings to be represented by at most $2N-1$ states and $O(N)$ transitions for a fixed alphabet.

Each state $v$ represents an end-position equivalence class: all non-empty substrings whose occurrence-ending sets are identical. len[v] is the maximum length in the class, while the minimum is len[link[v]] + 1. The suffix link points to the class of the longest proper suffix with a strictly larger end-position set.

When extending with symbol $c$, a new state represents the entire current prefix. If an existing transition reaches $q$ but len[p] + 1 != len[q], construction creates a clone with shortened maximum length, copied transitions, and the old suffix link. Redirecting appropriate transitions to the clone preserves deterministic transitions and the interval of lengths represented by every state.

class State:
    def __init__(self, length=0, link=-1):
        self.length = length
        self.link = link
        self.next = {}
        self.terminal_prefix = False
        self.first_position = -1


class SuffixAutomaton:
    def __init__(self, text=""):
        self.states = [State()]
        self.last = 0
        for position, symbol in enumerate(text):
            self.extend(symbol, position)

    def extend(self, symbol, position):
        current = len(self.states)
        self.states.append(State(self.states[self.last].length + 1))
        self.states[current].first_position = position
        self.states[current].terminal_prefix = True

        p = self.last
        while p != -1 and symbol not in self.states[p].next:
            self.states[p].next[symbol] = current
            p = self.states[p].link

        if p == -1:
            self.states[current].link = 0
        else:
            q = self.states[p].next[symbol]
            if self.states[p].length + 1 == self.states[q].length:
                self.states[current].link = q
            else:
                clone = len(self.states)
                self.states.append(State(self.states[p].length + 1, self.states[q].link))
                self.states[clone].next = self.states[q].next.copy()
                self.states[clone].first_position = self.states[q].first_position

                while p != -1 and self.states[p].next.get(symbol) == q:
                    self.states[p].next[symbol] = clone
                    p = self.states[p].link

                self.states[q].link = clone
                self.states[current].link = clone

        self.last = current

    def occurrence_counts(self):
        counts = [0] * len(self.states)
        for i, state in enumerate(self.states):
            if state.terminal_prefix:
                counts[i] = 1

        order = sorted(range(len(self.states)), key=lambda i: self.states[i].length, reverse=True)
        for state in order:
            parent = self.states[state].link
            if parent != -1:
                counts[parent] += counts[state]
        return counts

    def state_for(self, pattern):
        state = 0
        for symbol in pattern:
            if symbol not in self.states[state].next:
                return None
            state = self.states[state].next[symbol]
        return state


if __name__ == "__main__":
    sam = SuffixAutomaton("ababa")
    counts = sam.occurrence_counts()
    state = sam.state_for("aba")
    assert state is not None and counts[state] == 2
    assert len(sam.states) <= 2 * len("ababa") - 1

Substring Queries with Automaton DAG DP

Transition edges strictly increase len, so the SAM transition graph is a DAG. This permits dynamic programming in decreasing length order.

• Distinct substrings: Every non-empty path from the initial state spells one substring. With $dp[v]=1+\sum_{v\xrightarrow{c}u}dp[u]$, the answer is $dp[0]-1$ because the root's empty path must be excluded. Equivalently, $\sum_{v\ne0}(\operatorname{len}[v]-\operatorname{len}[\operatorname{link}[v]])$ counts the length interval contributed by each state.
• Pattern occurrence count: Follow the pattern to state $v$ and return $|\operatorname{endpos}(v)|$, obtained by propagating prefix-state counts through suffix links in decreasing len order.
• Longest common substring: Stream a second text through transitions, falling back through suffix links on mismatches while maintaining the current matched length.
• Lexicographic $k$-th substring: Cache the number of paths below every state and visit outgoing transitions in symbol order, skipping whole path-count blocks.
• Occurrence positions: first_position provides one occurrence. Reporting every occurrence requires additional end-position storage or traversal of the suffix-link tree and therefore incurs output-sensitive time and space.

BWT, Rank/Select, and the FM-Index

For a text $T=S\$$ with a unique smallest sentinel, sorting cyclic rotations is equivalent to sorting suffixes. The Burrows-Wheeler transform is

$$ L[i]=T[(\operatorname{SA}[i]-1)\bmod N]. $$

Let $C[c]$ count symbols in $T$ strictly smaller than $c$, and let $\operatorname{Occ}(c,i)$ count occurrences of $c$ in the half-open prefix $L[0\dots i)$. If $c=L[i]$, the LF mapping is

$$ \operatorname{LF}(i)=C[c]+\operatorname{Occ}(c,i). $$

The FM-index stores $L$, $C$, and a rank-capable representation such as a wavelet tree, wavelet matrix, or bitvector blocks. Backward search maintains a half-open suffix-array interval $[l,r)$, initially $[0,N)$. Reading pattern symbols right to left updates

$$ l\leftarrow C[c]+\operatorname{Occ}(c,l), \qquad r\leftarrow C[c]+\operatorname{Occ}(c,r). $$

The pattern is absent once $l\geq r$; otherwise it occurs $r-l$ times. Counting requires only rank queries. Locating positions additionally walks LF steps until reaching sampled suffix-array entries, so its time depends on the sampling rate.

Suffix trees favor direct navigation and rich topology, suffix automata favor substring-state DP, suffix arrays favor simplicity and cache locality, and FM-indexes favor compressed full-text search. Their asymptotic labels alone are insufficient: alphabet representation, sampling density, reporting requirements, construction memory, and constant factors determine the practical choice.