Suffix Automaton: The Compressed Map of Every Substring

What Problem Is the Suffix Automaton Solving?

Given a string of length n, the set of its distinct substrings can be enormous: up to roughly n squared over two of them for a string with no repeated characters. Storing them explicitly, one by one, is wasteful and often impossible for long texts. The suffix automaton sidesteps this by building a recognizer rather than a list. It is a deterministic finite automaton: a set of states connected by labeled transitions, with one designated initial state, such that following the transitions spelled out by any substring of the original string always lands on some state, and following the transitions spelled out by any non-substring gets stuck partway through. Crucially, every state that can be reached corresponds to accepting at least one substring, so every state is implicitly an accepting state for the substrings that lead to it.The genius of the construction is that even though the number of distinct substrings can be quadratic in n, the number of states in this automaton never exceeds roughly two times n minus one, and the number of transitions never exceeds roughly three times n minus four, for n greater than two. This is possible because a single state in the automaton represents an entire equivalence class of substrings that all happen to occur at exactly the same set of ending positions in the text. Two substrings collapse into the same state precisely when every occurrence of the shorter one is immediately followed by, or coincides with, every occurrence of the longer one in the text — formally, they share the same set of ending positions, called the endpos set. This equivalence is the conceptual heart of the whole structure: instead of representing substrings individually, the automaton represents endpos classes, and there simply are not that many of them.Because the automaton is deterministic, testing membership is mechanical and fast: start at the initial state, follow the transition labeled by each character of the candidate pattern in turn, and if you never fall off the automaton, the pattern is a substring. If any transition is missing, it is not. No backtracking, no comparisons beyond reading each character of the pattern once.

States, Endpos Classes, and the Suffix Link Tree

Each state of the suffix automaton corresponds to a nonempty set of substrings that share the same endpos set, and this set of substrings is always a contiguous range of lengths: the shortest and longest substrings mapped to a state, plus everything in between, all share that same endpos. A state therefore stores two lengths — the minimum and maximum length of the substrings it represents — and every substring in that range is obtained from the longest one by trimming characters off the front.This is where suffix links enter. Every state, except the initial one, has a suffix link pointing to the state representing the endpos class of its longest substring's longest proper suffix that belongs to a different, strictly larger endpos class. Following suffix links from any state walks through progressively shorter substrings with progressively larger (more general) endpos sets, and this chain always terminates at the initial state, which represents the empty string. The set of suffix links, taken together, forms a tree rooted at the initial state — often called the suffix link tree or the parent tree. This tree is not a side effect; it is a second, equally important structure layered on top of the automaton's transition graph, and many of the automaton's most useful computations are really tree computations performed on it.For instance, the number of times a given substring occurs in the original text equals the size of the endpos set of the state it maps to, and that size can be computed for every state simultaneously with a single bottom-up pass over the suffix link tree: leaves that correspond to positions where a suffix of the whole string ends contribute a count of one, and every internal state's count is the sum of its children's counts in the tree. This turns an occurrence-counting question, which sounds like it needs a text scan, into an elementary tree accumulation performed once after construction.

Building It Online, One Character at a Time

What makes the suffix automaton practical, not just theoretically elegant, is that it can be built incrementally. Start with an automaton for the empty string, consisting of a single initial state. Then extend it by appending characters one at a time: after processing a prefix of length k, the automaton on hand is exactly the suffix automaton for that prefix. Appending the next character updates it into the suffix automaton for the prefix of length k plus one, without ever revisiting earlier characters of the text.Each extension step creates a new state representing the whole prefix seen so far as a substring, then walks backward along suffix links from the previous end state, adding a transition on the new character wherever one is missing, until either running off the tree (reaching the initial state) or finding a state that already has a transition on the new character. In the latter case, a careful check determines whether that existing transition already represents exactly the right endpos class or whether it needs to be split into two states — one for the longer substrings that still share the old endpos set, and one, a clone, for the shorter substrings whose endpos set has just grown to include the new position. This cloning step is what keeps every state's substring range contiguous and every endpos class well defined, and it is the trickiest part of the algorithm to implement correctly.Despite the apparent complexity of individual steps, an amortized analysis (each character can only trigger a bounded amount of backward walking and cloning across the whole construction) shows the entire process runs in time linear in the length of the string, for any fixed-size alphabet, and uses linear space. This online property has a practical bonus: you can query the automaton for the text seen so far at any point during construction, which is exactly what streaming substring-matching applications need.

What You Can Compute Once It Is Built

With the automaton and its suffix link tree in hand, several classic string problems reduce to simple traversals. Substring testing: follow transitions labeled by the candidate pattern's characters from the initial state; success if you never get stuck, in time proportional to the pattern's length alone, regardless of how long the original text was. Counting distinct substrings: every state other than the initial one corresponds to a contiguous range of substring lengths (its length minus its suffix link's length many of them), so summing that quantity over all states gives the exact count of distinct substrings in the whole text, computed in time linear in the number of states. Counting occurrences of a specific substring: locate the state it maps to by following its characters, then read off the precomputed endpos-set size for that state (the bottom-up tree sum described earlier). Finding the lexicographically smallest or largest substring of a given length, or enumerating substrings in sorted order, can be done by walking the transition graph, since transitions out of a state are naturally ordered by character.Perhaps the most striking application is the longest common substring of two strings. Build the suffix automaton for the first string only. Then feed the second string into it as a read-only query stream: maintain a current state and a current match length, and for each character of the second string, try to extend the match; if the transition exists, extend; if not, fall back along suffix links (shortening the current match) until a matching transition is found or the initial state is reached. Tracking the best match length seen during this single pass over the second string yields the longest common substring of both strings in time linear in their combined length — no need to build any structure over the concatenation of both strings, and no separate structure needs to be built for the second string at all.

Suffix Automaton Versus Suffix Array: Two Views of the Same Substrings

This site already covers the suffix array, which sorts all n suffixes of a string lexicographically and pairs that sorted order with an LCP (longest common prefix) array recording, for each adjacent pair of sorted suffixes, how many leading characters they share. The suffix automaton and the suffix array both ultimately describe the same underlying object — the substring structure of a string — but they represent it in fundamentally different shapes, and it is worth contrasting them directly rather than treating them as interchangeable.A suffix array is fundamentally a list: n suffixes, sorted, each an entry pointing back into the text, plus the auxiliary LCP array of length n minus one. Its size is always exactly proportional to n, the length of the string, regardless of how repetitive or how varied the string's content is. A suffix automaton, by contrast, is a graph: its state count is bounded by roughly two times n, but for strings with heavy internal repetition, the actual number of states used is often far smaller than that bound, because many suffixes collapse into shared endpos classes. There is no equivalent collapsing available to the suffix array format, since it must always list every suffix as a distinct sorted entry — a suffix array for a string like twenty repetitions of the same letter still has as many entries as suffixes, while the corresponding suffix automaton stays extremely small since almost everything folds into a handful of states.The two structures also differ in what a single query costs. With a suffix array plus LCP array, testing whether a pattern of length m is a substring of the text typically uses binary search over the sorted suffixes, costing roughly m times the logarithm of n character comparisons (or m plus the logarithm of n with extra preprocessing). With a suffix automaton, the same test costs exactly m steps — one transition per character of the pattern — with no dependence on n at all beyond the automaton having already been built. The suffix automaton is also built online, extending naturally as characters arrive, whereas a suffix array is normally computed only once the whole string is known, using batch sorting-based algorithms. In short: reach for a suffix array when you want a stable, predictably sized, sorted view well suited to range and rank queries; reach for a suffix automaton when you want the smallest possible recognizer for substrings, especially for repetitive text, streaming construction, or per-pattern query time that ignores the text's total length.

Frequently asked questions

Try it live

Everything above runs in your browser — open Suffix Automaton: The Compressed Map of Every Substring and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.