Suffix Automaton — Building It One Character at a Time

States are endpos classes; each shows its len. Solid arrows are transitions, dashed gold arrows are suffix links. Watch the online extend and the clone/split when it fires.

step 0

Automaton & suffix-link tree

state (len shown) clone current (last) transition suffix link

States

distinct substrings so far = 0
states = 1   transitions = 0
Press Step to begin. We add characters left to right; each extend creates a new state and walks suffix links, sometimes cloning a state to split an endpos class.
Self-contained visualization. Distinct-substring count uses Σ (len[v] − len[link[v]]). The clone/split fires when the found transition leads to a non-solid state (len[q] ≠ len[p]+1). See junior.md and professional.md for proofs.