The Suffix Automaton

Imagine you need to answer the question "does this pattern appear anywhere in this text?" — thousands of times, for thousands of different patterns, all against the same long text. A naive search re-scans the text from scratch every time. A smarter idea: preprocess the text once into an index that answers each query instantly.

The suffix automaton (also called a DAWG — Directed Acyclic Word Graph) is the most elegant such index known. It is a finite-state machine — a compact directed graph — with one extraordinary property: a path through it spells out a string if and only if that string is a substring of the original text. Feed it any candidate pattern; if the automaton accepts it, the pattern is there.

What makes it remarkable is not what it does but how small it is. For a string of length $n$, the suffix automaton has at most $2n - 1$ states and at most $3n - 4$ transitions — proven limits, impossible to beat. And yet it is built in $O(n)$ time and space by a simple online algorithm: extend the automaton one character at a time, never looking back. Proved and published by Anatolii Blumer, Janet Blumer, Andrzej Ehrenfeucht, David Haussler, and Ross McConnell in 1985.

The suffix automaton sits in the heart of modern text processing — DNA search, plagiarism detection, data compression — and it connects deeply to the related concepts of pattern matching and sequence alignment.

Type any short string below and press Build. The demo constructs the suffix automaton state by state, then counts every distinct non-empty substring by summing, for each state, the difference between the longest and shortest strings it recognises.

<p class="hint">{{hint}}</p>
<div class="controls">
  <input id="inp" type="text" maxlength="15" value="abcbc" spellcheck="false" autocomplete="off" />
  <button id="build" type="button">{{btn_build}}</button>
  <button id="reset" type="button" class="ghost">{{btn_clear}}</button>
</div>
<div id="stats" class="stats"></div>
<div id="vis" class="vis"></div>
<div id="log" class="log"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; align-items: center; margin-bottom: .8rem; }
input { font: 600 15px ui-monospace, monospace; padding: .4rem .7rem;
        border: 1.5px solid #adb1b8; border-radius: 8px; width: 11rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.stats { font-size: .95rem; min-height: 1.4em; margin-bottom: .5rem; }
.stats b { color: #1d3557; }
.vis { overflow-x: auto; padding-bottom: .4rem; }
svg.aut { display: block; }
.log { font-size: .82rem; color: #555; margin-top: .6rem; line-height: 1.6;
       max-height: 90px; overflow-y: auto; }

// Code not found

Notice two things. First, the number of states grows at most linearly — never more than $2n - 1$ for a string of length $n$. Second, the distinct-substring count is computed in one linear pass over the automaton; brute-force enumeration would take $O(n^2)$ time just to list them. That gap — linear automaton vs quadratic enumeration — is the suffix automaton's superpower.

The suffix automaton is proven optimal — no smaller DFA can recognise exactly the substrings of any given string. The bounds are tight and elegant:

• States: at most $2n - 1$. The worst case is achieved by strings like aaa…ab — a run of one character followed by a single different one. Every state corresponds to an equivalence class of substrings that all end at exactly the same set of positions in the original string. These classes are called endpos classes, and partitioning all substrings into endpos classes is what produces the minimal automaton automatically.
• Transitions: at most $3n - 4$. Again tight in the worst case, and again a consequence of the endpos structure.
• Build time: $O(n)$. The online algorithm maintains a suffix link tree — a tree of endpos classes — and a pointer to the last created state. Each character extension does a bounded amount of work: follow suffix links, add at most two new states, redirect at most a constant number of transitions.
• The suffix link is the key insight: every state $v$ has a link to the state whose endpos class is the smallest proper superset of $v$'s endpos class. These links form a tree — the suffix link tree — that is also isomorphic to the suffix tree of the reversed string.

The result is a data structure that is simultaneously minimally sized, linearly built, and immediately queryable: pattern search is just one DFA traversal in $O(|P|)$ time, optimal by any measure. Compare this with the brute-force approach of enumerating all $O(n^2)$ substrings and storing them in a trie — the suffix automaton replaces exponential storage with linear storage while keeping query time constant per character.

The suffix automaton is not an academic curiosity — it is a workhorse behind several real-world systems:

• DNA and protein search: genomic databases store sequences hundreds of millions of characters long. Indexing a genome with a suffix automaton (or the related suffix array) lets a query like "does this gene fragment appear anywhere in the genome?" return in microseconds.
• Longest common substring: given two strings, you can find the longest string that is a substring of both by building the suffix automaton of one and running the other through it while tracking the longest accepted prefix. This runs in $O(n + m)$ time.
• Counting distinct substrings: the interactive demo above does this; the formula — sum over all states of (longest endpos length − suffix-link-parent's longest length) — gives the exact count in a single DFS.
• Data compression: the LZ-family of compression algorithms (the basis of ZIP, PNG, and gzip) rely on identifying repeated substrings. Suffix automata make that identification linear.
• Plagiarism and similarity detection: search engines and academic-integrity tools index documents with suffix structures to find copied passages efficiently.

Whenever the core task is "find or count substrings fast", the suffix automaton (or its close cousin the suffix tree, as in sequence alignment) is the standard choice.

The suffix automaton is one of the most elegant structures in theoretical computer science: a single finite-state machine, provably minimal, built in linear time, that silently encodes every substring of a given string in its transitions.

The size bounds — at most $2n - 1$ states, at most $3n - 4$ transitions — are not lucky engineering. They flow from the mathematics of endpos equivalence classes, and they cannot be improved. Every time a search engine, a genome browser, or a compression tool needs to find all occurrences of a pattern in a large corpus, it is, directly or indirectly, leaning on this structure.

Knowing the suffix automaton means knowing one of the places where theory and practice meet most cleanly — where the provably optimal solution is also the practically fast one.