Suffix Automaton (SAM)
A Suffix Automaton is the minimal deterministic finite automaton accepting all suffixes of a string, built online in linear O(n) time with at most 2n - 1 states to solve distinct substring, occurrence count, and LCS queries.
Difficulty: Hard · Interactive Visualizer · C++ / Python / Java / JS Code
Suffix Automaton (SAM)
A Suffix Automaton (SAM) of a string $S$ (length $n$) is the smallest deterministic finite automaton (DFA) that accepts every suffix of $S$—meaning every path starting from the initial state 0 spells out a unique substring of $S$! Remarkably, it has at most $2n - 1$ states and $3n - 4$ transitions, and can be constructed online (one character at a time) in $O(n)$ time!
At a Glance
| Property | Value |
| :--- | :--- |
| Build Time | $O(n)$ (online, character by character) |
| Max States / Transitions | $\le 2n - 1$ states, $\le 3n - 4$ transitions |
| Auxiliary Space | $O(n \cdot |\Sigma|)$ (or $O(n)$ with std::map transitions) |
| Best Used When | Counting distinct substrings online, $k$-th lexicographical substring, longest common substring in $O(n + m)$, occurrence counts |
---
How It Works
Each state u represents an equivalence class (endpos-class) of substrings that always end at the exact same set of positions in $S$. It stores:
len[u]: length of the longest substring in this class.link[u]: suffix link pointing to the state of the longest suffix ofuthat belongs to a strictly largerendposset.next[u][c]: transition on characterc.- Key Formula: State
urepresents exactlylen[u] - len[link[u]]distinct substrings!
When extending the SAM by character c (extend(c)):
1. Create new state cur with len[cur] = len[last] + 1.
2. Walk p = last upward via link[p] while p != -1 and next[p][c] is absent, setting next[p][c] = cur.
3. If p == -1, set link[cur] = 0.
4. Otherwise let q = next[p][c]. If len[p] + 1 == len[q], set link[cur] = q.
5. Else clone state q into a new state clone with len[clone] = len[p] + 1, redirect p's ancestors pointing to q toward clone, and set link[q] = link[cur] = clone.
6. Update last = cur.
---
Complexity & Key Insights
- Why
len[u] - len[link[u]]Counts Distinct Substrings Online: Every timeextend(c)finishes, the number of brand-new distinct substrings introduced by charactercis simplylen[cur] - len[link[cur]]! - Occurrence Count of Any Substring: Mark
occ[cur] = 1for every non-cloned state created inextend(c), then propagateocc[link[u]] += occ[u]in decreasing order oflen[u]! Walking any patternPfrom state0lands on stateuwhoseocc[u]is the exact frequency ofPin $S$ in $O(|P|)$ time!
---
Practice Problems
Easy
1. Count Distinct Substrings in $O(n)$
Compute the exact number of distinct non-empty substrings of s in linear time using a Suffix Automaton.
Approach: Build SAM with extend(c) and sum len[u] - len[link[u]] over all states u >= 1. Time: $O(n)$. Space: $O(n)$.
<details>
<summary>Show C++ Solution</summary>
#include <array>
#include <iostream>
#include <string>
#include <vector>
struct SAM {
struct State {
std::array<int, 26> next{};
int link = -1, len = 0;
State() { next.fill(-1); }
};
std::vector<State> st{1};
int last = 0;
void extend(char ch) {
int c = ch - 'a';
int cur = static_cast<int>(st.size());
st.emplace_back();
st[cur].len = st[last].len + 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 = static_cast<int>(st.size());
st.push_back(st[q]);
st[clone].len = st[p].len + 1;
while (p != -1 && st[p].next[c] == q) {
st[p].next[c] = clone;
p = st[p].link;
}
st[q].link = st[cur].link = clone;
}
}
last = cur;
}
long long countDistinctSubstrings() const {
long long total = 0;
for (size_t i = 1; i < st.size(); ++i) {
total += st[i].len - st[st[i].link].len;
}
return total;
}
};
int main() {
SAM sam;
for (char c : std::string("banana")) sam.extend(c);
std::cout << sam.countDistinctSubstrings() << "\n"; // 15
return 0;
}
</details>
2. Substring Existence Check in $O(|P|)$
Preprocess text T in $O(|T|)$ and answer whether any query pattern P is a substring of T in $O(|P|)$ time.
Approach: Walk transitions u = st[u].next[c - 'a'] from u = 0; return false if any transition is -1. Time: $O(|P|)$ per query.
<details>
<summary>Show C++ Solution</summary>
#include <array>
#include <iostream>
#include <string>
#include <vector>
struct SAM {
struct State {
std::array<int, 26> next{};
int link = -1, len = 0;
State() { next.fill(-1); }
};
std::vector<State> st{1};
int last = 0;
void extend(char ch) {
int c = ch - 'a', cur = static_cast<int>(st.size());
st.emplace_back(); st[cur].len = st[last].len + 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 = static_cast<int>(st.size());
st.push_back(st[q]); st[clone].len = st[p].len + 1;
while (p != -1 && st[p].next[c] == q) { st[p].next[c] = clone; p = st[p].link; }
st[q].link = st[cur].link = clone;
}
}
last = cur;
}
bool contains(const std::string& p) const {
int u = 0;
for (char c : p) {
u = st[u].next[c - 'a'];
if (u == -1) return false;
}
return true;
}
};
int main() {
SAM sam;
for (char c : std::string("abracadabra")) sam.extend(c);
std::cout << std::boolalpha << sam.contains("cadab") << " " << sam.contains("xyz") << "\n";
return 0;
}
</details>
---
Intermediate
3. Longest Common Substring of Two Strings in $O(n + m)$
Find the longest substring common to both a and b in strictly linear $O(n + m)$ time!
Approach: Build SAM on a, then stream b maintaining current state u and match length l. If next[u][c] exists, advance u and ++l; otherwise follow suffix links u = link[u] until a transition on c exists (resetting l = len[u] + 1). Track maximum l! Time: $O(n + m)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <array>
#include <iostream>
#include <string>
#include <vector>
struct SAM {
struct State {
std::array<int, 26> next{};
int link = -1, len = 0;
State() { next.fill(-1); }
};
std::vector<State> st{1};
int last = 0;
void extend(char ch) {
int c = ch - 'a', cur = static_cast<int>(st.size());
st.emplace_back(); st[cur].len = st[last].len + 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 = static_cast<int>(st.size());
st.push_back(st[q]); st[clone].len = st[p].len + 1;
while (p != -1 && st[p].next[c] == q) { st[p].next[c] = clone; p = st[p].link; }
st[q].link = st[cur].link = clone;
}
}
last = cur;
}
};
std::string longestCommonSubstringSAM(const std::string& a, const std::string& b) {
SAM sam;
for (char c : a) sam.extend(c);
int u = 0, curLen = 0, bestLen = 0, bestEnd = 0;
for (int i = 0; i < static_cast<int>(b.size()); ++i) {
int c = b[i] - 'a';
while (u != 0 && sam.st[u].next[c] == -1) {
u = sam.st[u].link;
curLen = sam.st[u].len;
}
if (sam.st[u].next[c] != -1) {
u = sam.st[u].next[c];
++curLen;
}
if (curLen > bestLen) { bestLen = curLen; bestEnd = i; }
}
return bestLen == 0 ? "" : b.substr(bestEnd - bestLen + 1, bestLen);
}
int main() {
std::cout << longestCommonSubstringSAM("ababc", "babca") << "\n"; // babc
return 0;
}
</details>
4. Count Occurrences of Any Query Pattern in $O(|P|)$
Preprocess text T in $O(|T|)$ and answer how many times any pattern P appears in T in $O(|P|)$ time.
Approach: Set occ[cur] = 1 on real states (and 0 on clones), sort states by len descending, and propagate occ[link[u]] += occ[u]. Then walk P from 0 and return occ[u]. Time: $O(|T|)$ build, $O(|P|)$ query.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
struct SAMCount {
struct State {
std::array<int, 26> next{};
int link = -1, len = 0;
long long occ = 0;
State() { next.fill(-1); }
};
std::vector<State> st{1};
int last = 0;
void extend(char ch) {
int c = ch - 'a', cur = static_cast<int>(st.size());
st.emplace_back(); 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 = static_cast<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 = st[cur].link = clone;
}
}
last = cur;
}
void finalizeCounts() {
std::vector<int> order(st.size());
std::iota(order.begin(), order.end(), 0);
std::sort(order.begin(), order.end(), [&](int a, int b) { return st[a].len > st[b].len; });
for (int u : order) {
if (st[u].link != -1) st[st[u].link].occ += st[u].occ;
}
}
long long count(const std::string& p) const {
int u = 0;
for (char c : p) {
u = st[u].next[c - 'a'];
if (u == -1) return 0;
}
return st[u].occ;
}
};
int main() {
SAMCount sam;
for (char c : std::string("banana")) sam.extend(c);
sam.finalizeCounts();
std::cout << sam.count("ana") << " " << sam.count("a") << " " << sam.count("z") << "\n"; // 2 3 0
return 0;
}
</details>
---
Hard
5. $k$-th Lexicographical Distinct Substring (SPOJ SUBLEX)
Find the $k$-th smallest distinct non-empty substring of s (1-indexed) in $O(|ans| \cdot |\Sigma|)$ per query after $O(n)$ preprocessing.
Approach: On the SAM DAG, compute paths[u] = number of distinct non-empty substrings reachable from u (1 + sum(paths[next[u][c]]) in reverse topological order of len). To find the $k$-th substring, start at u = 0 and greedily pick the smallest character c whose paths[next[u][c]] >= k (otherwise subtract paths[next[u][c]] from k)!
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
struct SAMKth {
struct State {
std::array<int, 26> next{};
int link = -1, len = 0;
State() { next.fill(-1); }
};
std::vector<State> st{1};
std::vector<long long> paths;
int last = 0;
void extend(char ch) {
int c = ch - 'a', cur = static_cast<int>(st.size());
st.emplace_back(); st[cur].len = st[last].len + 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 = static_cast<int>(st.size());
st.push_back(st[q]); st[clone].len = st[p].len + 1;
while (p != -1 && st[p].next[c] == q) { st[p].next[c] = clone; p = st[p].link; }
st[q].link = st[cur].link = clone;
}
}
last = cur;
}
void buildPaths() {
std::vector<int> order(st.size());
std::iota(order.begin(), order.end(), 0);
std::sort(order.begin(), order.end(), [&](int a, int b) { return st[a].len > st[b].len; });
paths.assign(st.size(), 1);
for (int u : order) {
for (int c = 0; c < 26; ++c) {
if (st[u].next[c] != -1) paths[u] += paths[st[u].next[c]];
}
}
}
std::string kthSubstring(long long k) const {
std::string res;
int u = 0;
while (k > 0) {
for (int c = 0; c < 26; ++c) {
int v = st[u].next[c];
if (v == -1) continue;
if (k <= paths[v]) {
res.push_back(static_cast<char>('a' + c));
--k; // count substring ending right here
u = v;
break;
}
k -= paths[v];
}
}
return res;
}
};
int main() {
SAMKth sam;
for (char c : std::string("abac")) sam.extend(c);
sam.buildPaths();
// Sorted distinct substrings of "abac": a, ab, aba, abac, ac, b, ba, bac, c
std::cout << sam.kthSubstring(1) << " " << sam.kthSubstring(4) << " " << sam.kthSubstring(9) << "\n";
return 0;
}
</details>
---
Related Algorithms
- Suffix Array — array-based sibling for LCP and pattern queries.
- Aho–Corasick Algorithm — multi-pattern automaton over a dictionary of words.