Suffix Automaton
A linear-time substring automaton that is especially good at online extension, distinct-substring counts, and occurrence queries.
Suffix Automaton
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Suffix automaton is the string structure I use when substring states matter more than lexicographic order. It stores all substrings of one string in a DAG of only \(O(n)\) states and is especially strong when the string is processed online.
Problem-Driven Motivation
Typical contest questions are:
how many distinct substrings does the string have,
how many times does a pattern occur as a substring,
what is the longest common substring with another string,
can the text be extended online while maintaining substring information.
Trying to treat every substring separately is hopeless because there are \(O(n^2)\) of them. The useful compression is to group substrings that behave the same with respect to ending positions.
Recognition Pattern
Suffix automaton is a strong fit when:
the base string is scanned left to right,
the queries are about substrings as automaton states, not about lexicographic suffix order,
distinct-substring counting or occurrence aggregation is central,
online extension is valuable.
If the problem is mainly about lexicographic order or suffix sorting, suffix array is often the cleaner tool.
Derivation
The core abstraction is the \(\texttt{endpos}\) equivalence class:
Two substrings belong to the same state if they end at exactly the same set of positions in the full string.
Each state stores:
len[v]: the maximum length in the class,link[v]: the suffix link to the largest proper suffix class,transitions by characters.
When appending one new character:
one new terminal state is created,
suffix links are followed backward to add missing transitions,
sometimes an existing state must be cloned because one old equivalence class actually splits into two classes.
The clone is the subtle part. It appears exactly when an old state would otherwise claim a shortest representative that is too long, breaking the automaton invariant.
Worked Problem
Problem.
Build one text \(s\), then answer many pattern queries asking how many times each pattern appears in \(s\).
Why naive fails.
Running a separate linear scan for every pattern is too slow when both the text and the query count are large.
Step 1: build the suffix automaton of the text.
After processing the whole text, every substring corresponds to some path from the start state.
Step 2: propagate occurrence counts.
While extending, each new terminal state contributes one end position. After building the automaton, propagate those counts backward in decreasing \(\texttt{len}\) order along suffix links.
Why this propagation is correct.
If state \(v\) has suffix link \(p\), then every occurrence represented by \(v\) also contributes to the suffix-class represented by \(p\). So counts must flow from longer states to shorter suffix-link parents.
Step 3: answer pattern queries.
Walk the pattern along automaton transitions. If a transition is missing, the pattern is absent. Otherwise the final state's propagated count is exactly the number of occurrences.
Implementation Reasoning
The meanings of the fields matter more than the code shape:
len[v]tells the largest length in the state,len[link[v]] + 1 \ldots len[v]is the full range of lengths represented by the state,occ[v]counts end positions only after the propagation pass.The clone step copies transitions and the suffix link, but resets
occto zero because the clone is a structural split, not a new end position.
Correctness Intuition
The automaton stays minimal because states are exactly the end-position equivalence classes. Appending one character only creates one genuinely new family of substrings: the suffixes ending at the new last position. Everything else is reused, except when a previous state must be cloned to preserve correct suffix-link structure.
The formula \[ \sum_{v \ne root} \bigl(len[v] - len[link[v]]\bigr) \] counts distinct substrings because each state contributes exactly the lengths that appear first in that state and in no shorter suffix-link ancestor.
Complexity Analysis
build: \(O(n)\) states and transitions for a fixed alphabet representation,
occurrence propagation: \(O(n)\),
one pattern existence or occurrence query: \(O(|pattern|)\).
Common Pitfalls
Initializing clone states incorrectly.
Forgetting that
occis not ready until the propagation pass is done.Using suffix automaton for lexicographic tasks that are simpler with suffix array.
Hard-coding an alphabet that does not match the problem.
Variants and Failure Modes
Longest common substring can be solved by walking a second string over the automaton.
The suffix-link tree supports additional DP after the automaton is built.
If the problem is about palindromes, palindromic tree is the right analog instead.
Practice Problems
Count distinct substrings.
Count occurrences of many patterns in one text.
Longest common substring or repeated-substring tasks.
References
Code
Contest-ready reference implementation for the idea explained above.
#include <bits/stdc++.h>
using namespace std;
struct SuffixAutomaton {
struct State {
int link = -1;
int len = 0;
int occ = 0;
array<int, 26> next{};
State() {
next.fill(-1);
}
};
vector<State> st;
int last = 0;
SuffixAutomaton() {
st.push_back(State{});
}
void extend(char ch) {
int c = ch - 'a';
int cur = (int)st.size();
st.push_back(State{});
st[cur].len = st[last].len + 1;
st[cur].occ = 1;
int p = last;
while (p != -1 && st[p].next[c] == -1) {
st[p].next[c] = cur;
p = st[p].link;
}
if (p == -1) {
st[cur].link = 0;
} else {
int q = st[p].next[c];
if (st[p].len + 1 == st[q].len) {
st[cur].link = q;
} else {
int clone = (int)st.size();
st.push_back(st[q]);
st[clone].len = st[p].len + 1;
st[clone].occ = 0;
while (p != -1 && st[p].next[c] == q) {
st[p].next[c] = clone;
p = st[p].link;
}
st[q].link = clone;
st[cur].link = clone;
}
}
last = cur;
}
void build(const string& s) {
for (char ch : s) extend(ch);
}
bool contains(const string& s) const {
int v = 0;
for (char ch : s) {
int c = ch - 'a';
if (st[v].next[c] == -1) return false;
v = st[v].next[c];
}
return true;
}
long long count_distinct_substrings() const {
long long answer = 0;
for (int v = 1; v < (int)st.size(); ++v) {
answer += st[v].len - st[st[v].link].len;
}
return answer;
}
void propagate_occurrences() {
int max_len = 0;
for (const State& state : st) max_len = max(max_len, state.len);
vector<int> cnt(max_len + 1, 0), order(st.size());
for (const State& state : st) ++cnt[state.len];
for (int i = 1; i <= max_len; ++i) cnt[i] += cnt[i - 1];
for (int i = (int)st.size() - 1; i >= 0; --i) {
order[--cnt[st[i].len]] = i;
}
for (int i = (int)order.size() - 1; i > 0; --i) {
int v = order[i];
int p = st[v].link;
if (p != -1) st[p].occ += st[v].occ;
}
}
int occurrences_of(const string& pattern) const {
int v = 0;
for (char ch : pattern) {
int c = ch - 'a';
if (st[v].next[c] == -1) return 0;
v = st[v].next[c];
}
return st[v].occ;
}
};
// Example application: count occurrences of many patterns in one fixed text.
vector<int> count_occurrences_of_patterns(const string& text, const vector<string>& patterns) {
SuffixAutomaton sam;
sam.build(text);
sam.propagate_occurrences();
vector<int> answer;
answer.reserve(patterns.size());
for (const string& pattern : patterns) {
answer.push_back(sam.occurrences_of(pattern));
}
return answer;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.