Suffix Automaton

endpos classes · linear substring engine

1:00

How to build the smallest DFA that recognizes every substring of a string, count distinct substrings in linear time, and answer powerful string queries with a single linear-size structure.

By the end, you can

Explain why the suffix automaton accepts every substring (not just suffixes) and why it is the smallest such DFA.
Define endpos(t) and explain why substrings with the same endpos set collapse into one state.
Trace the online construction of the suffix automaton for a short string, including when and why the clone step fires.
Compute the number of distinct substrings using the len − len(link) formula.
Identify the correct suffix automaton-based algorithm for occurrence count, longest common substring, and longest repeated substring queries.
State the size bounds (2n − 1 states, 3n − 4 transitions) and build time (O(n)) from memory and explain why they hold.
Describe the relationship between the suffix automaton, the suffix tree, and the suffix array.

Up next in String Algorithms, Advanced DP & Competitive Techniques