Suffix Tree — Ukkonen's Online Construction

Add characters of S$ one at a time. Watch the global end extend leaves, the active point move, Rule 2 splits create internal nodes, and suffix links (dashed purple) appear.

step 0

Suffix tree of S$ (under construction)

internal node leaf active point suffix link leaf edge (global end)

Algorithm state

phase (char index i)-
adding character-
global end (leafEnd)-1
remaining0
active_noderoot
active_edge-
active_length0
rule appliedstart
nodes / leaves1 / 0
Press Step to begin. Ukkonen processes S$ left to right, keeping the suffix tree of every prefix.
Self-contained visualization. The three tricks: global end (leaf edges share one end index, extended for free each phase), suffix links (dashed purple, O(1) hops between node "xα" and "α"), and the active point (active_node, active_edge, active_length) with skip/count. See middle.md and professional.md.