Suffix automaton

A suffix automaton is a minimal partial deterministic finite automaton accepting the suffixes of a fixed string. Every path from its initial state spells a substring; marking every state accepting therefore recognizes all substrings, though that altered automaton need not be minimal for the larger language.

For a nonempty substring $u$, let $\mathrm{endpos}(u)$ be the set of positions where an occurrence ends. End-position equivalence groups substrings with the same such set into one state. In ababa, b and ab both end at positions two and four, so they share a state. A character transition extends each represented occurrence; a suffix link leads to the class of the longest suffix outside the current class.^[ref]

This represents many substrings with only linearly many states and transitions. The documented incremental construction creates a state for a newly appended character and, when needed, a clone separating incompatible continuation histories. With a fixed finite alphabet it takes $O(n)$ time for a length-$n$ string. A membership query follows the proposed string's character transitions and fails at the first missing transition.^[ref]

In a suffix automaton, a suffix link from state $v$ leads to the state containing the longest suffix of its longest represented string that lies in a different end-position equivalence class. If $L(v)$ is the maximum represented length, state $v$ represents one string at each length from $L(\mathrm{link}(v))+1$ through $L(v)$. Following links strictly decreases length and eventually reaches the initial state.^[ref]

For ababa, the state representing ababa also represents baba; its link leads to the state containing aba. This skips a suffix already in the current class. The links form a rooted tree useful for propagating occurrence counts from longer matches to shorter suffixes.

Two nonempty substrings have end-position equivalence when their sets of occurrence-ending positions in one fixed text are equal. This is the grouping used for states of a suffix automaton, with an additional initial state. In ababa, using one-based positions, b and ab both end at $\{2,4\}$, whereas a ends at $\{1,3,5\}$. Thus b and ab share a state despite their different lengths.^[ref]

Equality of ending sets ensures that appending the same character gives equal new ending sets whenever the extension occurs. This makes character transitions well defined. Within a class the represented strings are nested suffixes, one at every length in an interval; suffix links connect that interval to the next shorter class.