Home▸Algorithms & AI▸Suffix Automaton: The Compressed Map of Every Substring

🧬 Suffix Automaton: The Compressed Map of Every Substring

Explore the suffix automaton, the smallest deterministic finite automaton that recognizes every substring of a string, built online in linear time using suffix links.

Algorithms & AI3DModerate60 FPS

The simulator builds a suffix automaton live as you type a string character by character, drawing each new state and its transitions, highlighting the suffix link walked back during cloning, and visually distinguishing cloned states from newly created ones so you can watch endpos classes split apart in real time.

🔬 What It Demonstrates

🎮 How to Use

Type or load a sample string, then step forward one character at a time (or press play for continuous animation) to watch the automaton grow. Click any state to see the range of substring lengths it represents and its outgoing transitions; toggle the suffix link tree overlay to see the parent-pointer structure separately from the transition graph. Enter a candidate pattern to trace its automaton walk and see instantly whether it is a substring, and switch to comparison mode to feed a second string in and watch the longest common substring get tracked live.

💡 Did You Know?

For a string of length n, a suffix automaton never needs more than roughly two times n minus one states, no matter the alphabet size, and for a string made of one character repeated n times, it collapses all the way down to just n plus one states total.

⚙ Under the hood

Explore the suffix automaton, the smallest deterministic finite automaton that recognizes every substring of a string, built online in linear time using suffix links.

stringsautomata theorysuffix structureslinear timepattern matchinggraph theorytext indexing

3D · Three.js / WebGL renderer · 60 FPS target · runs fully client-side, no install