Suffix automaton
= Suffix automaton
= SAM
{c}
{synonym}
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 $\operatorname{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.<Suffix Automaton in the CP-Algorithms documentation>[Definition, Substring property, End positions and Suffix links]{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.<Suffix Automaton in the CP-Algorithms documentation>[Construction in linear time; Implementation; Check for occurrence]{ref}