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.
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.
Text input for the source string, step/play/pause/reset controls for incremental construction, a speed slider, a toggle for the suffix link tree overlay, a pattern-search box with live automaton-walk tracing, and a two-string comparison mode for longest common substring.
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.
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.
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.
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.
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.