What is a Suffix Automaton?
Learn what a suffix automaton is, how it compactly encodes all substrings, and how to answer this advanced string algorithm question.
Expected Interview Answer
A suffix automaton is the smallest deterministic finite automaton that accepts exactly every suffix of a given string, built online in O(n) time and space, and it compactly represents all distinct substrings of the string as paths from its initial state.
Each state in a suffix automaton represents an equivalence class of substrings that all occur at exactly the same set of ending positions in the source string, so instead of storing every one of a string's O(n²) substrings explicitly, the automaton merges them into at most 2n-1 states connected by suffix links, which point from a state to the state representing its longest common suffix class. Building it incrementally, one character at a time, using clone operations to split states when a new character breaks an equivalence class, is what keeps construction linear despite the automaton implicitly encoding a quadratic number of substrings. Once built, it answers substring existence in O(m) time for a query of length m, counts distinct substrings, finds the longest common substring between two strings, and finds the longest repeated substring, all in linear or near-linear time. This makes it the tool of choice whenever a problem needs to reason about “all substrings” of a string without ever materializing them.
- Represents all O(n²) substrings in O(n) states
- Built online in O(n) time and space
- Answers substring queries in O(m) time
- Solves longest repeated / common substring efficiently
AI Mentor Explanation
A suffix automaton is like a coach maintaining one compact diagram of every possible “form segment” a batter has shown across an entire season, where segments that always occurred at the exact same set of match moments are merged into a single state rather than tracked separately. Adding a new innings to the record does not mean rebuilding the whole diagram — the coach updates it incrementally, occasionally cloning a state when a new shot pattern needs to be distinguished from an existing one. Suffix links in this diagram point from a specific shot sequence to the more general pattern it is a special case of, letting the coach instantly generalize or specialize when comparing form. This lets the coach answer “has this shot sequence ever occurred” in time proportional only to the sequence length, without ever listing every possible sub-sequence explicitly.
Step-by-Step Explanation
Step 1
Start with a single initial state
The automaton begins representing only the empty string.
Step 2
Extend one character at a time
Create a new state for the extended string, then walk suffix links updating transitions.
Step 3
Clone states when needed
If a transition leads to a state representing a longer class than needed, clone it to split the equivalence class correctly.
Step 4
Use suffix links for queries
Traverse states and suffix links to count distinct substrings, find longest repeats, or compare two strings.
What Interviewer Expects
- Explain that states represent equivalence classes of substrings by ending positions
- State the O(n) time/space and at most 2n-1 states bound
- Explain the role of suffix links and cloning during online construction
- Give a use case: distinct substring counting, longest repeated substring, longest common substring
Common Mistakes
- Confusing a suffix automaton with a suffix tree or suffix array (related but distinct structures)
- Thinking it stores substrings explicitly rather than as equivalence classes
- Forgetting the clone operation, which is required to keep construction correct and linear
- Overestimating query cost — substring existence is O(m), not O(n)
Best Answer (HR Friendly)
“A suffix automaton is a compact structure that represents every possible substring of a string using a small number of linked states, built in linear time as you read the string once. I would use it for problems like counting distinct substrings or finding the longest repeated substring, where listing all substrings directly would be far too slow.”
Code Example
class State:
__slots__ = ('link', 'len', 'trans')
def __init__(self):
self.link = -1
self.len = 0
self.trans = {}
class SuffixAutomaton:
def __init__(self):
self.states = [State()]
self.last = 0
def extend(self, ch):
cur = len(self.states)
self.states.append(State())
self.states[cur].len = self.states[self.last].len + 1
p = self.last
while p != -1 and ch not in self.states[p].trans:
self.states[p].trans[ch] = cur
p = self.states[p].link
if p == -1:
self.states[cur].link = 0
else:
q = self.states[p].trans[ch]
if self.states[p].len + 1 == self.states[q].len:
self.states[cur].link = q
else:
clone = len(self.states)
self.states.append(State())
self.states[clone].len = self.states[p].len + 1
self.states[clone].trans = dict(self.states[q].trans)
self.states[clone].link = self.states[q].link
while p != -1 and self.states[p].trans.get(ch) == q:
self.states[p].trans[ch] = clone
p = self.states[p].link
self.states[q].link = clone
self.states[cur].link = clone
self.last = cur
def build(self, s):
for ch in s:
self.extend(ch)
return self
def count_distinct_substrings(self):
return sum(self.states[v].len - self.states[self.states[v].link].len for v in range(1, len(self.states)))Follow-up Questions
- How would you find the longest common substring of two strings using a suffix automaton?
- How does a suffix automaton differ from a suffix tree in structure and use cases?
- How would you count the number of distinct substrings using the automaton's states?
- How does the clone operation guarantee the automaton stays linear in size?
MCQ Practice
1. What is the maximum number of states in a suffix automaton for a string of length n?
A suffix automaton for a string of length n has at most 2n - 1 states, keeping the structure linear in size.
2. What does each state in a suffix automaton represent?
States group together substrings that always occur ending at exactly the same positions in the source string.
3. What is the time complexity to build a suffix automaton for a string of length n?
The automaton is built online, one character at a time, in amortized O(n) time and space.
Flash Cards
What does a suffix automaton represent? — The smallest DFA accepting exactly all suffixes of a string, encoding all distinct substrings.
What is the maximum number of states for a string of length n? — At most 2n - 1 states.
What operation keeps construction correct when splitting equivalence classes? — Cloning a state when a transition points to a class that is too long.
Name one problem a suffix automaton solves efficiently. — Counting distinct substrings, or finding the longest repeated/common substring.