Skip to content
Tutorials Center
My learning

Topics

Lesson 206 of 225 ยท Advanced Topics

Suffix Automaton

Build a suffix automaton in linear time, check substring queries in O(m), and count distinct substrings and occurrences, with fully runnable Python code.

A suffix array answers substring questions by sorting suffixes. The suffix automaton (SAM) takes a different route: it is the smallest deterministic automaton that accepts exactly the suffixes of a string, and it is built online, one character at a time, in O(n) time and with at most 2n - 1 states. Once you have it, any substring query costs O(length of the query), and counting distinct substrings becomes a short loop.

Suffix automata look intimidating because the construction has a few subtle cases. The trick is to learn the idea first, then the code: what a state means, what a suffix link is, and why cloning a state keeps everything consistent. You should be comfortable with tries, string basics and amortized analysis before reading on.

Substrings as states

Every substring t of a string s has an end-position set: the indexes in s where an occurrence of t ends. Two substrings with the same end-position set are indistinguishable for the future: whatever character you append, they behave the same way. A SAM has one state for each distinct end-position set.

For s = "abcbc", the substrings bc and c both end at positions 2 and 4 (0-based), so they share a state. The substring abc ends only at position 2, so it has its own state. All the strings in one state are suffixes of the longest one, and their lengths form a continuous range from len(link) + 1 up to len(state).

Each state stores:

  • len: the length of the longest substring in the state;
  • next: transitions on characters, like a trie edge;
  • link: the suffix link, pointing to the state of the longest suffix of this state's strings that has a different end-position set.
flowchart LR
    S0(("0<br/>empty")) -- a --> S1(("1<br/>a"))
    S1 -- b --> S2(("2<br/>ab"))
    S2 -- c --> S3(("3<br/>abc"))
    S3 -- b --> S4(("4<br/>cb, bcb, abcb"))
    S4 -- c --> S6(("6<br/>abcbc and its<br/>longer suffixes"))
    S0 -- b --> S5(("5<br/>b"))
    S5 -- c --> S7(("7<br/>c, bc"))
    S0 -- c --> S7
    S7 -- b --> S4
    S3 -. link .-> S7
    S6 -. link .-> S7
    S7 -. link .-> S0

The full automaton for "abcbc" (8 states). The strings "c" and "bc" share state 7; dotted arrows are some of the suffix links.

The construction

Keep a pointer last to the state of the whole string so far. To append character c:

  1. Create a new state cur with len = len(last) + 1.
  2. Walk p = last and follow suffix links. As long as p has no transition on c, add p -> cur on c.
  3. If you fall off the root, set link(cur) = root. Otherwise let q = next[p][c].
    • If len(p) + 1 == len(q), then q already holds exactly the right strings: link(cur) = q.
    • Otherwise clone q into clone with len = len(p) + 1, copying its transitions and link. Redirect q and cur to use clone as their link, and redirect transitions p -> q along the suffix-link chain to p -> clone.
  4. Set last = cur.

The clone step splits a state whose strings would otherwise disagree about the next character. Although the inner loops look expensive, the total work over all appends is O(n) amortized, the same kind of argument as the one for KMP.

Python Building a suffix automaton

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The automaton for a string of length n >= 2 has at most 2n - 1 states and 3n - 4 transitions, so memory stays linear.

Substring queries

To check whether t is a substring of s, start at the root and follow the characters of t. If you can follow all of them, t occurs; if a transition is missing, it does not. That is O(|t|), independent of the length of s. If you want suffix membership instead, also require that the final state is terminal, meaning it lies on the suffix-link chain from last.

Python Substring and suffix queries

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Counting distinct substrings

Each state represents len(v) - len(link(v)) different strings (the lengths from len(link) + 1 to len(v)). Different states represent disjoint sets of strings, so the number of distinct non-empty substrings is the sum of that quantity over all states except the root. This is O(n) once the automaton is built, compared with O(n log n) or more via a suffix array.

You can also count how many times each substring occurs. Give every non-clone state an occurrence count of 1 and every clone 0. Then process states in decreasing order of len and add each state's count to its suffix link's count. The count of a state is the number of occurrences of every string in it.

flowchart TD
    A["Non-clone state: cnt = 1<br/>clone: cnt = 0"] --> B["Sort states by len, descending"]
    B --> C["For each state v:<br/>cnt[link v] += cnt[v]"]
    C --> D["cnt[v] = number of occurrences<br/>of the strings in v"]

Occurrence counts flow up the suffix-link tree, longest states first.

Python Distinct substrings and occurrences

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check by hand: aaaa has 4 distinct substrings (a, aa, aaa, aaaa), and banana has 15 (21 substrings with repeats, minus duplicates).

SAM or suffix array?

Both solve the same family of problems. A suffix array is smaller in memory and has no tricky construction, and with an LCP array it can answer most queries. A suffix automaton is simpler for online problems (the string grows) and for problems that compare two strings: build the SAM of one, then walk the other through it to find the longest common substring in O(n + m). Its transition maps cost more memory in Python than a flat array.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does a state of a suffix automaton represent?

    Substrings with identical end-position sets behave identically for any continuation, so they are merged into one state.
  2. 2. What is the maximum number of states in the suffix automaton of a string of length n (n >= 2)?

    Each append creates one new state and at most one clone, which gives at most 2n - 1 states in total.
  3. 3. How many distinct non-empty substrings does the automaton represent?

    A state holds the strings with lengths len(link)+1 through len(v), so this difference counts them, and states never share strings.
  4. 4. Why is a state cloned during construction?

    When len(p) + 1 is smaller than len(q), only the shorter suffixes of q are affected by the new character, so q is split.

Summary

  • A suffix automaton is the minimal DFA of all suffixes of a string, built online in O(n) with at most 2n - 1 states.
  • States group substrings by end-position set; each state keeps len, transitions and a suffix link.
  • Appending a character adds a state, adds transitions up the suffix-link chain and sometimes clones a state.
  • Substring queries take O(|t|); distinct substrings are the sum of len(v) - len(link(v)); occurrence counts come from propagating along suffix links.

Next: van Emde Boas Trees and Y-fast Tries