Suffix Automaton

The smallest deterministic automaton recognizing every substring of a string, built online in linear time.

What it is

A suffix automaton (SAM) of string S is the minimal deterministic finite automaton whose accepted language is exactly the set of substrings of S. Despite recognizing quadratically many substrings, it has at most 2n-1 states and 3n-3 transitions, and it is built incrementally in O(n) over a fixed alphabet.

Endpos classes and suffix links

Each state corresponds to a set of substrings that share the same set of end positions in S, called an endpos class. States are linked by suffix links that point to the state of the longest proper suffix in a different endpos class. This link tree is the reversed structure of the suffix tree of the reversed string, which is why the SAM answers many suffix-tree queries.

Online extension

The automaton is extended one character at a time. Adding a character creates a new state and follows suffix links from the previous end, either adding transitions or cloning a state when a transition already leads to a longer string. The clone step is what keeps the automaton minimal.

# state fields: len, link, next{char: state}
def sa_extend(c, st, last):
    cur = new_state(length=st[last]['len']+1)
    p = last
    while p != -1 and c not in st[p]['next']:
        st[p]['next'][c] = cur
        p = st[p]['link']
    # ... clone logic sets links to keep the automaton minimal
    return cur

Applications

• Count distinct substrings by summing len(state) minus len(link) over all states.
• Find the longest common substring of two strings by feeding one through the other's automaton.
• Count occurrences of a pattern by precomputing endpos sizes over the link tree.
• Locate the k-th lexicographically smallest substring by counting paths.