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]