Why this matters when you build with AI
A common check in AI products is whether a phrase appears in a source text. A retrieval step asks whether a quoted line is copied word for word from a document. A moderation or quality step asks how many times a banned phrase occurs in a batch of transcripts. Each of these is a substring question, and it is often asked many times over the same text.
The suffix automaton is a structure for these questions. It is built from the text one character at a time, it has at most about twice as many states as the text has characters, and once it is built a membership test walks a single path of states. Counting how often a substring occurs takes one more pass over the states. The structure also grows as the text streams in, so it can answer questions about the prefix seen so far.
The risk is in the details. The construction has one step, cloning, that is easy to skip, and the code still runs without it on many inputs. A skipped clone gives a wrong answer that looks fine on a short example. The tests in this lesson exist for that reason.
The idea
States group substrings with the same ending places
Take a text s and a substring t. Its end positions are the positions where an occurrence of t ends. Positions are counted from 1. In the text abcbc, the substring c ends at positions 3 and 5, and the substring bc ends at 3 and 5 too. The substring b ends at 2 and 4.
The suffix automaton puts every substring into a state, and two substrings share a state exactly when they have the same set of end positions. A state holds a range of lengths. In abc the state that holds c also holds bc and abc, because all three end only at position 3. Let len(v) be the length of the longest string in state v. The state holds the suffixes of that longest string whose lengths lie between len(link(v)) + 1 and len(v).
Each state has three fields that matter:
len: the length of the longest string in the state.link: the suffix link, which points to the state of the longest string that is a proper suffix of this state's strings but sits in a different state. Itslenis smaller.next[c]: the transition by letterc, which points to the state that contains the string plusc.
The root is state 0, the state of the empty string. Its link is -1.
A worked example: three letters
Feed abc into the automaton. After a, there is one new state, 1, with len = 1 and link = 0. After ab, state 2 has len = 2. Its link is 0, because no shorter suffix of ab ends at the same places, so this state holds both ab and b. After abc, state 3 has len = 3 and link 0. It holds abc, bc and c, which all end at position 3 and nowhere else.
The real output for abc is one state for each prefix plus the root. The next section shows the step in code, and the clone case, which needs one more idea.
The online extend step
Adding one character c to the text, with last the state of the whole text so far, takes these steps:
- Create a new state
curwithlen = len(last) + 1. - Walk the suffix links from
last. For each statepwith no transition byc, setp.next[c] = cur. Stop at the first statepthat already has a transition byc, or whenpbecomes -1. - If no such state was found, set
link(cur) = 0. - Otherwise let
q = p.next[c]. Iflen(p) + 1 == len(q), setlink(cur) = q. This is the simple case. - If
len(p) + 1 < len(q), stateqholds strings that are too long for this position. Make a clone: a new state withlen = len(p) + 1, a copy ofq's transitions, andq's link. Walk the links frompagain and redirect every transition bycthat points toqso that it points to the clone. Then setlink(q) = link(cur) = clone.
Step 5 is cloning. It splits q so that the strings that end at the new position get their own state.
Here is the real trace for abcbc. The lines show the last two extend steps, from the fourth letter on. The fourth letter b triggers a clone, which is state 5.
after 'b': 6 states
state 0 len=0 link=-1
state 1 len=1 link=0 (prefix)
state 2 len=2 link=5 (prefix)
state 3 len=3 link=0 (prefix)
state 4 len=4 link=5 (prefix)
state 5 len=1 link=0
after 'c': 8 states
state 0 len=0 link=-1
state 1 len=1 link=0 (prefix)
state 2 len=2 link=5 (prefix)
state 3 len=3 link=7 (prefix)
state 4 len=4 link=5 (prefix)
state 5 len=1 link=0
state 6 len=5 link=7 (prefix)
state 7 len=2 link=0Read the step after the fourth letter. Before it, state 2 holds ab and b, with len = 2 and link 0, and both end at position 2. After the new b, the substring b also ends at position 4, but ab does not. So the state must split: the clone is state 5 with len = 1, holding b. State 2 keeps only ab, and its link becomes 5. The new state 4 for abcb also links to 5.
Size of the automaton
Each extend step adds the state cur, plus at most one clone. So the automaton for a text of length n has at most 2n + 1 states, counting the root. My tests (below) never found more than 2n - 1 states for a text of length 2 or more. I did not prove that tighter bound here, so I state only the tested part. On my random test text of one million characters, the count was about 1.35 times the text length.
The standard technique: the code
The code below is the whole structure: the extend step, a membership test, and the occurrence count. It uses a 26-letter alphabet of lowercase letters, so each state holds 26 transitions as plain integers. The count_endpos method runs after the text is built, and it sorts the states by len with a comparison sort, which is simple and fast enough for the sizes in this lesson.
// Suffix automaton over the alphabet 'a'..'z', built online one character at a time.
#include <bits/stdc++.h>
struct SuffixAutomaton {
struct State {
int len; // length of the longest string in this state
int link; // suffix link: the state of the longest proper suffix in another class
int next[26]; // transitions, -1 if missing
int endpos_count; // filled by count_endpos()
bool is_prefix; // true for states created as "cur" (they end at a prefix of s)
};
std::vector<State> st;
int last = 0;
static State make(int len, int link, bool is_prefix) {
State s;
s.len = len;
s.link = link;
std::fill(std::begin(s.next), std::end(s.next), -1);
s.endpos_count = 0;
s.is_prefix = is_prefix;
return s;
}
SuffixAutomaton() { st.push_back(make(0, -1, false)); }
void extend(char ch) {
int c = ch - 'a';
int cur = st.size();
st.push_back(make(st[last].len + 1, -1, true));
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 {
// q is too long to be the link: split it with a clone that has the shorter length.
int clone = st.size();
State copy = st[q];
copy.len = st[p].len + 1;
copy.is_prefix = false;
st.push_back(copy);
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 std::string& s) {
for (char ch : s) extend(ch);
}
// Returns the state reached by reading p from the start, or -1 if p is not a substring.
int walk(const std::string& p) const {
int v = 0;
for (char ch : p) {
v = st[v].next[ch - 'a'];
if (v == -1) return -1;
}
return v;
}
bool contains(const std::string& p) const { return walk(p) != -1; }
// endpos_count[v] = number of end positions of the strings in state v.
// Each prefix state adds 1, then the counts flow up the suffix links, longest states first.
void count_endpos() {
int n = st.size();
std::vector<int> order(n);
std::iota(order.begin(), order.end(), 0);
std::sort(order.begin(), order.end(), [&](int x, int y) { return st[x].len > st[y].len; });
for (int v = 0; v < n; v++) st[v].endpos_count = st[v].is_prefix ? 1 : 0;
for (int v : order)
if (st[v].link != -1) st[st[v].link].endpos_count += st[v].endpos_count;
}
// Number of (possibly overlapping) occurrences of p in the built text. Needs count_endpos() first.
long long occurrences(const std::string& p) const {
int v = walk(p);
return v == -1 ? 0 : st[v].endpos_count;
}
};The make helper fills every new state with -1 transitions, which is how the code tells a missing transition from a real one. The clone copies q with State copy = st[q] before pushing, so the copy is taken before the vector may move in memory.
Membership
walk starts at the root and follows one transition per letter of the pattern. If a transition is missing, the pattern is not a substring, and the function returns -1. If every letter is followed, the state it ends in contains the pattern. The walk costs O(|p|), the length of the pattern, and does not depend on the text length.
Counting occurrences
Each state v has a set of end positions. Count them as follows. Every state created as cur has an end position at the step that created it, so it gets a count of 1. Clones do not get that count, because a clone is made from an existing state, not from a new end position. Then, going from the longest state down to the shortest, each state adds its count to its link. When the walk is done, the count of a state is the number of end positions of the strings it holds.
The count for a substring is then the count of the state the walk ends in. In abcbc, b ends at positions 2 and 4. The state for b is the clone 5. States 2 and 4 both link to it, and each was created as a prefix state with count 1, so the clone's count is 2. The next section shows what happens when clones are counted as end positions.
Worked problem: count the occurrences of each pattern
Statement (my own). You get a text s of length n, with 1 <= n <= 100000, made of lowercase letters. Then you get q patterns, with 1 <= q <= 100000, each made of lowercase letters with total length up to 300000. For each pattern print the pattern and the number of times it occurs in s, counting overlapping occurrences. A pattern that does not occur has count 0.
Input format. The first line holds s. The second line holds q. Each of the next q lines holds one pattern.
Sample input (the four lines below):
banana
4
an
a
na
xExpected output, from the program run on this input:
an 2
a 3
na 2
x 0Check it by hand. an occurs at positions 2 and 4 (counted from 1), so 2. a occurs three times. na occurs at positions 3 and 5, so 2. x does not occur, so 0.
The program is:
#include "sam.h"
using namespace std;
// Worked problem: read text s, then q patterns. Print how many times each pattern occurs in s.
int main() {
string s;
cin >> s;
SuffixAutomaton sam;
sam.build(s);
sam.count_endpos();
int q;
cin >> q;
while (q--) {
string p;
cin >> p;
cout << p << " " << sam.occurrences(p) << "\n";
}
}It builds the automaton once and answers each pattern with one walk. The total time is O(n + total pattern length), with the alphabet size fixed at 26.
Complexity
- Build: O(n) time for the extend steps, with the alphabet fixed. Each step adds at most two states, and the walks over suffix links are amortised O(1) per character, since a link walk that goes up must have been preceded by a link walk that went down.
- Counting end positions: O(number of states) plus the sort. The code uses a comparison sort, which adds O(n log n). A counting sort by
lengives O(n) and is the usual choice in contests. - Membership and count per pattern: O(length of the pattern).
- Memory: 120 bytes per state for the struct above, which holds 26 transition integers, three more integers and a flag, padded to 120 bytes.
I measured the build on my test machine (WSL2 Linux, g++ 15.2, -O2). Your numbers will differ.
sizeof(State)=120 bytes
n=1000000 random: states=1346964 (bound 2n-1=1999999)The random text of one million characters gives 1346964 states, below the bound of 2n - 1 = 1999999. Re-measured with the same compiler and flags on another random text, the build took about 1 second and count_endpos about 0.4 seconds.
Where AI tools go wrong
An AI assistant often writes the extend step with the clone branch missing, or with the clone not copying the transitions. A bug can pass a short example by chance. The missing transition copy failed only on a random 20-letter string. Here is what the real test printed when I removed that copy from the code above and ran the randomized test from the exercise:
missing substring in ccabcacbaaabacaaabab
exit=1The test stops at the first string where a substring is not found, and prints it. The second bug is counting clones as end positions, which the next section shows with real output, including two strings where the bug gives correct counts.
Ask for the code and the test together, and check the test on small strings. A prompt that works well:
Write a C++17 suffix automaton over lowercase letters, with an extend step that clones
the state when the link is not direct. Add a count_endpos method that counts end positions
using the prefix states only, and a walk method for membership.
Also write a brute-force test that generates 5000 random strings of length 1 to 30 over
a 3-letter alphabet, checks that every substring is found, checks 40 random patterns
against a naive overlapping count, and checks that the state count is at most 2n - 1
for strings of length 2 or more.
A good answer compiles with -O2, prints one line for a passing run, and names the first
failing string when a test fails. Read the clone branch yourself: it must copy the
transitions of q, redirect the transitions that point to q, and set both links.Common mistakes
Counting clones as end positions
Symptom: a substring count is too large. The clone is not a place where a substring ends, so it must not get a count of 1. Here is the real output from the test program with every state marked as a prefix state, on three short strings. Each line gives the number of substrings with a wrong count, and the first one found.
aabaa: 0 substrings with a wrong count, first:
abcbc: 6 substrings with a wrong count, first: b buggy=3 correct=2
abab: 0 substrings with a wrong count, first: Look at abcbc. The substring b occurs at positions 2 and 4, so the true count is 2. The buggy version gives 3, because the clone for b got a count of 1 that does not belong to it. The aabaa and abab strings happen to give correct counts, so a passing example does not prove the code is right.
Forgetting the last state
After the loop over the text, last is the state of the whole text. It is not needed by walk and count_endpos in this code, but a version that uses it to answer queries about the whole text must set it correctly after each extend. Check that last = cur runs at the end of extend, not inside a branch.
Using the wrong alphabet offset
The code uses ch - 'a'. A text with capital letters, digits or spaces indexes outside the 26 transitions, which is undefined behaviour in C++. Map the alphabet first, or use a larger transition table for your input.
Copying a state by reference
st[cur].link = clone after st.push_back is safe because the code uses indices, not references. A reference taken before a push_back can point to memory that the vector has moved. The code copies st[q] into a local State before the push.
Hands-on exercise
Work on your own machine. Save sam.h from above into a folder, then save the randomized test below as sam_test.cpp and compile:
g++ -O2 -std=c++17 -Wall -Wextra -o sam_test sam_test.cpp
./sam_test#include "sam.h"
using namespace std;
long long naive_occ(const string& s, const string& p) {
long long c = 0;
for (size_t i = 0; i + p.size() <= s.size(); i++)
if (s.compare(i, p.size(), p) == 0) c++;
return c;
}
int main() {
mt19937 rng(2024);
long long pattern_checks = 0;
int max_states_ratio_ok = 0;
for (int iter = 0; iter < 5000; iter++) {
int n = rng() % 30 + 1;
int sigma = rng() % 3 + 1;
string s(n, 'a');
for (char& ch : s) ch = 'a' + rng() % sigma;
SuffixAutomaton sam;
sam.build(s);
sam.count_endpos();
// State bound: at most 2n - 1 states for n >= 2 (n = 1 has 2 states).
int states = sam.st.size();
int limit = n >= 2 ? 2 * n - 1 : 2;
if (states > limit) { printf("too many states on %s\n", s.c_str()); return 1; }
max_states_ratio_ok++;
// Every substring must be found; random strings must agree with a naive search.
for (int a = 0; a < n; a++)
for (int len = 1; a + len <= n; len++)
if (!sam.contains(s.substr(a, len))) { printf("missing substring in %s\n", s.c_str()); return 1; }
for (int q = 0; q < 40; q++) {
int m = rng() % 4 + 1;
string p(m, 'a');
for (char& ch : p) ch = 'a' + rng() % (sigma + 1);
bool want_in = naive_occ(s, p) > 0;
if (sam.contains(p) != want_in) { printf("membership mismatch %s in %s\n", p.c_str(), s.c_str()); return 1; }
if (sam.occurrences(p) != naive_occ(s, p)) { printf("count mismatch %s in %s\n", p.c_str(), s.c_str()); return 1; }
pattern_checks++;
}
}
printf("all tests passed: 5000 strings, %lld pattern checks, state bound held on %d strings\n", pattern_checks, max_states_ratio_ok);
}A correct build prints one line:
all tests passed: 5000 strings, 200000 pattern checks, state bound held on 5000 stringsThen do three things. First, trace aab by hand: write the states after each letter, with len and link, and compare with the real states below. Second, make the clone start empty instead of copying the transitions of q (use make(st[p].len + 1, st[q].link, false)), as in the section on AI mistakes above, and confirm the test fails. Third, add a method that returns the number of distinct substrings of s by summing len(v) - len(link(v)) over all non-root states, and check it against a naive count on the random strings. The method is a preview of a later lesson, and checking it here is good practice.
The real states for aab, after the three letters:
state 0: len=0 link=-1
state 1: len=1 link=0
state 2: len=2 link=1
state 3: len=3 link=0
a^1: states=2
a^2: states=3
a^3: states=4
a^4: states=5
a^5: states=6
a^6: states=7
longest repeated: 3000 random strings, 0 mismatches
banana: 3
aaaa: 3The first four lines of that output are the states for aab. The rest are used in the practice section below.
Checklist
- Does
extendcreatecurbefore walking the links, and setlast = curat the end? - Does the clone copy the transitions and the link of
q, and getlen = len(p) + 1? - Does the redirect loop stop when
pis -1 or when the transition does not point toq? - Do both
link(q)andlink(cur)point to the clone? - Are only the states created as
curmarked as prefix states? - Does the count pass visit states from longest to shortest?
- Does a random test with a 2-letter alphabet pass for strings up to length 30?
Practice
Practice 1: trace aab
Write the states of the automaton after a, aa and aab, with len and link. Say which step adds a new state and which step, if any, clones.
Hint: after aa, the state for aa has link to the state for a. When b arrives, walk the links from the previous state and look for a transition by b.
Show the answer
After aab there are four states: the root, then a (len 1, link 0), aa (len 2, link 1), and aab (len 3, link 0). The b step adds state 3 and sets the transition by b in states 2, 1 and 0. No clone is made: the walk ends at -1 without finding a transition by b, so the link of state 3 is 0. These are the four states printed above.
Practice 2: states for a run of the same letter
For the text a repeated n times, how many states does the automaton have, counting the root?
Hint: each new a extends the longest state by one letter, and no clone is needed.
Show the answer
It has n + 1 states, since each letter adds one state and the root is state 0. The real output for n from 1 to 6 is 2, 3, 4, 5, 6 and 7 states, which is n + 1 in every case.
Practice 3: the longest repeated substring
Write a function that returns the length of the longest substring that occurs at least twice in the text, using the automaton. Test it against a naive method on random strings.
Hint: the states with an end-position count of at least 2 hold the substrings that occur twice. The longest of them is the answer, and it is the largest len among those states.
Show the answer
The function builds the automaton, runs count_endpos, and takes the maximum len over non-root states with a count of at least 2. This is the solution I tested:
int longest_repeated(const std::string& s) {
SuffixAutomaton sam;
sam.build(s);
sam.count_endpos();
int best = 0;
for (size_t v = 1; v < sam.st.size(); v++)
if (sam.st[v].endpos_count >= 2) best = std::max(best, sam.st[v].len);
return best;
}Its real output from the test program, which compares it against a naive method on 3000 random strings:
state 0: len=0 link=-1
state 1: len=1 link=0
state 2: len=2 link=1
state 3: len=3 link=0
a^1: states=2
a^2: states=3
a^3: states=4
a^4: states=5
a^5: states=6
a^6: states=7
longest repeated: 3000 random strings, 0 mismatches
banana: 3
aaaa: 3The line longest repeated: 3000 random strings, 0 mismatches is the check. The line banana: 3 is right, because ana occurs at positions 2 and 4.
Practice 4: why the prefix flag exists
Explain why a clone must not be counted as an end position. Use the abcbc example and the real output from the bug program.
Hint: count the end positions of b by hand, then ask which state gets the extra count in the buggy version.
Show the answer
The substring b ends at positions 2 and 4, so its true count is 2. A clone is created when a state is split, and it holds strings that already had their end positions before the new letter. Its count comes only from the states below it in the link tree. If the clone also gets a count of 1, every state that links to it gains an extra end position that does not exist. In abcbc the buggy count for b is 3, against the correct 2. The real output: abcbc: 6 substrings with a wrong count, first: b buggy=3 correct=2.
aabaa: 0 substrings with a wrong count, first:
abcbc: 6 substrings with a wrong count, first: b buggy=3 correct=2
abab: 0 substrings with a wrong count, first: Summary
The suffix automaton groups substrings by their end positions, and the extend step with cloning keeps those groups correct as the text grows. Membership is a walk, and counting is one pass over the states from longest to shortest.