Suffix Automata and Counting Distinct Substrings Online

A text of length n has Θ(n²) distinct substrings, and a structure that lists them explicitly cannot be smaller than quadratic. A suffix automaton does not list them: it represents the set of substrings as paths in a directed acyclic graph with at most 2n−1 states and 3n−4 transitions, and the count of distinct substrings becomes a sum over states rather than an enumeration. The same graph answers occurrence counting and longest-common-substring queries, and it is built by appending characters one at a time, which makes it the natural index for text that arrives as a stream.

The construction is short — a few dozen lines — but it is opaque unless the invariant behind the cloning step is understood. That invariant is the equivalence of end-position sets.

States as sets of end positions

For a text T, the end-position set of a substring s, written endpos(s), is the set of positions where an occurrence of s ends. Two substrings are equivalent if their end-position sets are equal. The equivalence classes are the states of the automaton.

Two facts follow immediately. First, substrings in the same class have different lengths and one is a suffix of the other, because occurrences ending at the same positions and differing in length must share those endings. Each state therefore represents a contiguous range of lengths from a minimum to a maximum, and the maximum is the state’s length. Second, for any state, the set of substrings it represents is exactly the suffixes of its longest string whose lengths fall in that range.

The second fact explains why a state needs one link and not many. The suffixes of a state’s longest string that are shorter than its minimum belong to other states, and those states are reached by following a suffix link. The link of a state points to the state representing the longest proper suffix of its longest string that falls in a different class. Following links from any state enumerates all suffixes of its longest string in decreasing length, and terminates at the initial state, which represents the empty string with the end-position set containing every position.

The number of states is at most 2n−1 because each appended character adds at most one state and at most one clone, and the number of transitions is at most 3n−4 for n ≥ 3. The two bounds are tight for different texts: abbb…b reaches 2n−1 states, while a text such as abbb…bc reaches 3n−4 transitions.

The append operation and the cloning case

Extending the text by a character c requires creating a new state for the whole text, then wiring transitions from every state that represents a suffix of the previous text and has no c-transition. The walk follows suffix links from the last state until it reaches a state that already has a c-transition or the initial state.

When the walk finds a state q with a c-transition to some state p, two cases arise. If len(q) + 1 equals len(p), then p already represents exactly the right range of lengths and the new state’s suffix link points to p. If len(q) + 1 is less than len(p), p represents a range that straddles the boundary: the strings of length len(q)+1 now occur at the new end position and the longer ones do not. The automaton splits p into two states — a clone with length len(q)+1 inheriting p’s transitions and link, and p itself with its length unchanged — and redirects the transitions that led to p through the clone. The clone is the new state’s suffix link, and p’s suffix link becomes the clone.

The split is what keeps end-position sets equal within each state. Before the extension, p’s strings all ended at the same set of positions. After it, the shorter strings also end at the new position and the longer ones do not, so the old class no longer describes a single end-position set. Cloning restores the invariant by separating the two.

class SuffixAutomaton:
    def __init__(self):
        self.link = [-1]
        self.length = [0]
        self.next = [{}]
        self.last = 0

    def extend(self, c):
        cur = len(self.link)
        self.link.append(0); self.length.append(self.length[self.last] + 1)
        self.next.append({})
        p = self.last
        while p != -1 and c not in self.next[p]:
            self.next[p][c] = cur
            p = self.link[p]
        if p == -1:
            self.link[cur] = 0
        else:
            q = self.next[p][c]
            if self.length[p] + 1 == self.length[q]:
                self.link[cur] = q
            else:
                clone = len(self.link)
                self.link.append(self.link[q])
                self.length.append(self.length[p] + 1)
                self.next.append(dict(self.next[q]))
                while p != -1 and self.next[p].get(c) == q:
                    self.next[p][c] = clone
                    p = self.link[p]
                self.link[q] = clone
                self.link[cur] = clone
        self.last = cur

The redirection loop is the part that looks arbitrary. It resumes at the state p where the first loop stopped and continues walking the suffix chain, rewriting every transition that goes to q so that it goes to the clone instead. Those are exactly the states whose c-transition should now land in the shorter class: the extended text’s suffixes that are one character longer than a suffix already in p’s class. The walk stops at the first state whose transition is not q, and it may run past the initial stop of the first loop only if q was reached through an existing transition. Transitions from that point onwards, and from unrelated states, keep pointing at q.

Counting distinct substrings

Each state other than the initial one represents a set of substrings of lengths from len(link(state)) + 1 to len(state). Every distinct substring belongs to exactly one state, so the count is the sum of len(state) − len(link(state)) over all states except the initial one.

def distinct_substrings(sam):
    return sum(sam.length[v] - sam.length[sam.link[v]]
               for v in range(1, len(sam.length)))

For abracadabra the sum is 54 distinct substrings, out of the 66 substrings counted with multiplicity (n(n+1)/2), and the automaton for the text has 12 states, the same as the number of characters plus the initial state. The saving is against the number of substrings rather than against n: the state count is at most 2n−1 even though the text has n(n+1)/2 substrings. For aaaa…a the automaton has n+1 states, and the distinct substring count is only n. The count is available at any prefix of the text, which means a program can report the number of distinct substrings of every prefix in linear total time.

The same sum weighted differently gives other quantities. Summing len(state) − len(link(state)) multiplied by the size of the state’s end-position set gives the number of distinct substrings counted with multiplicity, and the maximum len over states whose end-position set has at least two members gives the longest repeated substring.

End-position counts and occurrence queries

The size of a state’s end-position set is the number of occurrences of any string it represents, because all strings in a state have the same end positions. The sizes are computed by propagating counts along suffix links in decreasing order of length: each state’s count starts at one if it was created as a non-clone state during construction, zero if it is a clone, and then each state adds its count to its link’s target. Processing states in decreasing len order guarantees a state’s count is complete before it is propagated.

The initial state’s count is the text length after propagation, since the empty string ends everywhere. This propagation is linear in the number of states, so the whole index costs O(n) time and space.

Occurrence queries then follow a path from the initial state labelled by the pattern; if the path exists, the pattern occurs, and the count at the final state is the number of occurrences. A failed transition means the pattern does not occur. The query cost is O(|P|) with no dependence on n beyond the graph size, which is stronger than the O(|P| log n) of a suffix array binary search.

Where the automaton beats the array, and where it does not

The automaton is built incrementally and supports appending. The suffix array and the Burrows–Wheeler index built from it do not: appending one character can change the rank of every suffix, so their order has to be recomputed. For a text that grows — a log being scanned, a buffer being filled — the automaton is the structure that fits without periodic rebuilding.

It does not support arbitrary edits. A single extend call runs in amortised constant time, but deleting or changing a character in the middle invalidates the end-position sets of an unbounded number of states. For a mutable text, neither structure works without a dynamic index, and practical systems use a balanced structure over blocks with a static index per block.

It also does not preserve the lexicographic order that makes the suffix array useful for range queries over the text itself. The automaton’s transitions are unordered; a lexicographic traversal of the suffix array is what full-text search uses, and the Burrows–Wheeler transform is defined on that order, not on the automaton.

Two implementation hazards are worth stating. The clone’s transition map must be copied, not shared, because later redirections mutate the clone’s map independently of the original’s. And the length of a clone is len(p) + 1; using len(q), which can exceed len(p) + 1, produces an automaton whose substring counts are wrong while the transition structure still looks correct.

The construction is also the reason the Aho–Corasick failure links look familiar: suffix links and failure links are the same idea, applied to a trie of patterns in one case and to the set of all substrings in the other. Aho–Corasick’s failure link points to the longest proper suffix that is a trie node; a suffix automaton’s link points to the longest proper suffix in a different equivalence class. The difference in the target condition is what makes one an index of a dictionary and the other an index of a text.

Matching a pattern with a fixed number of mismatches

A less obvious use of the automaton is approximate matching of a pattern against the indexed text. The table is indexed by automaton state and by pattern position: D[v][i] is the minimum number of edits needed to turn the first i characters of the pattern into some string that labels a path from the initial state to v. States are processed in order of length, which is a topological order of the transition graph, so every entry is final before it is read. Each entry is the minimum of three candidates: a transition into v on character c from a predecessor u, costing D[u][i-1] plus one if c differs from the pattern’s i-th character; the same predecessor with no pattern character consumed, costing D[u][i] + 1 for a character deleted from the text; and D[v][i-1] + 1 for a pattern character with no text character, an insertion. The answer for a state is its row’s entry for the full pattern, and the minimum over all states is the best approximate match anywhere in the text.

The cost is O(states × |P|), which is O(n·|P|) since the state count is linear in the text: the same shape of work as filling the full edit-distance table, but over a graph whose size is linear in the text instead of products of pattern and text prefixes. It is the same recurrence that bit-parallel methods accelerate by packing a whole column into machine words; here the column is indexed by state instead of by pattern position, and no packing applies. The automaton version extends to any pattern length and any budget, and pays for that generality with a memory-resident table; the bit-parallel version does a constant number of word operations per text character but is bounded by the word size without blocking.