Suffix Automaton

Worked Example

For the text "abb", the suffix automaton represents all its substrings: "", "a", "b", "ab", "bb", and "abb".

1. Start with an empty automaton consisting of just the root state (length 0).
2. Add "a": create a state for "a". Length is 1.
3. Add "b": create a state for "ab". Length is 2. The suffix link points to a new state for "b".
4. Add "b": create a state for "abb". Length is 3. The suffix link points to a state for "bb". A clone state is created because the previous transition wasn't contiguous.

The total number of states is 5 (including the root), with 1 clone state. Distinct substrings are 5.

Experiment

Observe the automaton construction and properties for different strings.

1. Select a string from the Text dropdown, such as "ababa".
2. Observe the resulting number of distinct substrings, states, and clones.

Try it out in the Interactive Suffix Automaton Module.

Limitations

This interactive module processes very short strings (length at most 5) to visualize the construction clearly. In practice, suffix automata can handle texts with millions of characters efficiently, but visualizing them at that scale requires advanced layout algorithms or collapsing subgraphs.

References

The following resources provide more rigorous definitions and algorithms related to suffix automata and string algorithms.

• NIST Dictionary of Algorithms and Data Structures: suffix automaton