Why this matters when you build with AI
Ask an AI assistant to count how often each word from a list of 1000 words appears in a long text, and it will often write a loop: for each word, search the text. That is correct, and it is slow. With a text of 10^6 characters and 1000 words, the loop does about 10^9 character comparisons in the worst case. The program runs for minutes where it should take a fraction of a second. Nothing in the output warns you about the time.
The fix is a structure built for many patterns at once, called Aho-Corasick. It is also where AI-written code tends to fail in a quiet way. The usual bug is a missing step that drops matches. A pattern that sits inside a longer match, such as "he" inside "she", is counted zero times. The output looks plausible, and the total is just a little too small.
This lesson builds the structure from the simplest piece, the trie, and then shows how to find the bug above by running a test that compares against a slow, simple check.
The idea in plain words
A trie (pronounced "try") is a tree that stores a set of words by their prefixes. Each path from the root spells a prefix. A node marks the end of a word when a word stops there. For the words "he", "she", "his" and "hers", the trie looks like this:
root
|- h -- i -- s* ("his" ends here)
| `- e* ("he" ends here)
`- s -- h -- e* ("she" ends here)
`- ... ("hers" continues from "he")The nodes marked with * end a word. Note that "he" is a prefix of "hers", so the node for "he" also leads to a node for "hers" through r and s. The trie stores the shared prefix "he" once. A search costs time proportional to the length of the word, no matter how many words are stored.
Alphabet tries and binary tries
An alphabet trie has one child slot for each letter. For lowercase letters, a node holds 26 child pointers. Inserting or finding a word of length L takes O(L) steps.
A binary trie is the same idea over the bits of numbers. Each node has two children, for bit 0 and bit 1. A number with 31 bits is a path of 31 steps from the root. Binary tries answer questions like "which stored number is closest to this one in XOR?", and the practice problem at the end uses one.
A small example of an alphabet trie
Insert "he" and then "she". The path for "he" is root, h, e. The path for "she" is root, s, h, e. These share no nodes, so the trie has two separate branches. Now insert "hers". Its path starts root, h, e, which already exists, then r, s. The h and e nodes are shared. Each word adds only the nodes it does not already have.
From one word to many: failure links
A trie can find the words in a set, but it does not find words inside a longer text. Scanning a text with a trie means starting at the root for every position. That costs the length of the longest pattern times the length of the text.
Aho-Corasick fixes this with failure links. For a node v that spells the string x, the failure link fail[v] is the node for the longest proper suffix of x that is also a prefix in the trie. "Proper" means shorter than x itself.
A worked example with the four words above. Take the node she, which spells "she".
- Its suffixes, from longest to shortest, are "she" (not proper), "he", "e", and the empty string.
- "he" is a node in the trie, so
fail[she]is the nodehe.
The node he says: the last two characters read are "he", and "he" is a word. So when the text has just read "she", the matcher already knows that "he" ended at the same position. A failure link carries that knowledge without a second search.
Another example: the node hi, which is the prefix of "his". Its suffixes are "i" and the empty string. No node i exists in the trie, so fail[hi] is the root.
Computing failure links in BFS order
Failure links are computed breadth first, from the root outwards. A node's failure link points to a node that is shallower, so that node is finished before the node that uses it. The first level, the children of the root, all have failure link the root. For any other node u with parent v and letter x, the failure link is found by following fail[v] and taking the x child, going up the failure chain until a node has that child. The code does this with the goto table described next, so each step is a single lookup.
The goto automaton
The goto automaton fills every missing child with a link to where the matcher would go next. For a node v and a letter x:
- if the trie has a child
xofv, the goto is that child; - otherwise the goto is the goto of
fail[v]on the letterx.
With this table, reading the text is one table lookup per character, with no loops or backtracking. The state after reading any prefix of the text is the longest suffix of that prefix that is a node in the trie. Here is the state sequence for "ushers" with the four words above:
text: u s h e r s
state: root s sh she her hersAfter she the state is the node she, and the node she has a word ending at it. The node he is on its failure chain, so "he" also ends there. The next section shows how to count both without a loop.
Counting every occurrence: dictionary links
At each text position the matcher is in one state. Several words can end at that position: at the end of "ushers" both "she" and "he" end at position 3 (counting from 0), and "hers" ends at position 5. A word ends at a state if its node is the state itself or any node on its failure chain.
Walking the failure chain at each position works but can be slow. The standard trick is to count visits and then push the counts up the failure tree. The matcher counts how many text positions ended in each state. Then, processing the states from deepest to shallowest, each state adds its count to the state of its failure link. When this is done, the count of a node is the number of text positions where the node's string occurred, because every occurrence of a longer string also ends at all its suffixes that are nodes.
The code below does exactly this. The failure links point to shallower nodes, so processing the nodes in reverse BFS order adds each count into a node that is processed later. In textbooks this shortcut is often described with dictionary links, which jump directly to the next state on the failure chain that ends a word. Both give the same counts.
The standard code: Aho-Corasick with counts
The program reads the text, the number of patterns m, and the patterns. It prints the number of occurrences of each pattern (overlaps included) and the total. It uses 26 lowercase letters. We compiled it with g++ -O2 -std=c++17 -Wall -Wextra with no warnings.
// Aho-Corasick over lowercase letters. Counts occurrences of every pattern
// in a text (overlaps included) and prints per-pattern counts and the total.
#include <bits/stdc++.h>
using namespace std;
struct AhoCorasick {
static const int SIG = 26;
vector<array<int, SIG>> go; // trie edges, then full goto after build
vector<int> fail, order; // failure links and BFS order
vector<int> visits; // how many text positions ended at each node
vector<int> endNode; // trie node that ends pattern i
AhoCorasick() { newNode(); }
int newNode() {
array<int, SIG> row;
row.fill(-1);
go.push_back(row);
fail.push_back(0);
visits.push_back(0);
return (int)go.size() - 1;
}
void addPattern(const string& p) {
int v = 0;
for (char c : p) {
int x = c - 'a';
if (go[v][x] == -1) {
int u = newNode(); // may reallocate go, so index again below
go[v][x] = u;
}
v = go[v][x];
}
endNode.push_back(v);
}
// BFS: set failure links and turn missing edges into goto transitions.
void build() {
queue<int> q;
order.clear();
for (int x = 0; x < SIG; x++) {
if (go[0][x] == -1) go[0][x] = 0;
else {
fail[go[0][x]] = 0;
q.push(go[0][x]);
}
}
while (!q.empty()) {
int v = q.front();
q.pop();
order.push_back(v);
for (int x = 0; x < SIG; x++) {
int u = go[v][x];
if (u == -1) {
go[v][x] = go[fail[v]][x];
} else {
fail[u] = go[fail[v]][x];
q.push(u);
}
}
}
}
// Walk the text once. O(text length) transitions.
void run(const string& text) {
int v = 0;
for (char c : text) {
v = go[v][c - 'a'];
visits[v]++;
}
// Push visit counts up the failure tree: a node's visits also count
// for every node on its failure chain. Reverse BFS order does this.
vector<long long> acc(go.size());
for (size_t i = 0; i < visits.size(); i++) acc[i] = visits[i];
for (int i = (int)order.size() - 1; i >= 0; i--) {
int v2 = order[i];
acc[fail[v2]] += acc[v2];
}
visits.assign(acc.begin(), acc.end());
}
long long countOf(int i) const { return visits[endNode[i]]; }
};
int main() {
string text;
int m;
cin >> text >> m;
AhoCorasick ac;
vector<string> pats(m);
for (int i = 0; i < m; i++) {
cin >> pats[i];
ac.addPattern(pats[i]);
}
ac.build();
ac.run(text);
long long total = 0;
for (int i = 0; i < m; i++) {
printf("%s %lld\n", pats[i].c_str(), ac.countOf(i));
total += ac.countOf(i);
}
printf("total %lld\n", total);
return 0;
}What we checked
Worked example. For the text ushers and the patterns he, she, his, hers, the program printed:
he 1
she 1
his 0
hers 1
total 3These are the right answers. "he" and "she" both end at position 3, and "hers" ends at position 5.
Random tests. We wrote a Python checker that counts overlapping occurrences by comparing every start position. We ran 500 random cases: texts of length 1 to 60 over the alphabets and , with 1 to 6 patterns of length 1 to 5. The program and the checker agreed on every per-pattern count and on the total, with 0 mismatches.
Timing. We ran the program on a text of 1000000 random characters over with 10 random patterns of length 8. It printed a total of 39241 occurrences and took about 0.04 seconds on our WSL machine. Time depends on the machine, so treat this as one data point. It shows that the cost does not grow with the number of patterns in the way the naive loop does.
Worked problem: occurrences of a dictionary
Here is the problem in full, written for this lesson.
Input: a line with a text T of lowercase letters, with the length of T at most 10^6. Then a line with an integer m, and m lines with one pattern each. Patterns are lowercase, the total length of all patterns is at most 10^6, and a pattern may appear more than once in the input. Output: for each pattern in input order, the number of positions where it starts in T, with overlaps counted. Then print the total over all patterns.
Solution. Build the goto automaton from the patterns. Run the text through it, counting how often each state is reached. Push the counts up the failure tree. Each pattern's answer is the count of its end node. The total is the sum of the answers. The two pieces of work are: build in O(26 * total pattern length) time, and run in O(length of T) time plus the reverse pass over the nodes.
A small check by hand: with ushers, the state counts are 1 at she, 1 at her and 1 at hers, and 0 elsewhere, after the text is read. The reverse pass adds the count of she into he, since he is the failure link of she. So he gets 1, she gets 1, hers gets 1 and his gets 0. That is the output above.
Duplicates need no special case: two identical patterns end at the same node and both read the same count.
Complexity
Building the trie and the goto table costs time and memory proportional to the number of nodes times the alphabet size of 26. The number of nodes is at most the total pattern length plus one. Matching costs O(length of T), and counting costs O(number of nodes).
Memory is the real limit. Each node stores 26 integers of 4 bytes, which is 104 bytes. A dictionary with 10^6 total pattern characters has up to 10^6 nodes, so about 104 MB for the goto table alone. Check the memory limit of your contest. If it is too small, store the children of each node in a sorted list or a hash map, which uses less memory per node but makes each step slower.
Common mistakes
Only the first mistake below was run in our scratch folder. The symptoms of the others are what the algorithm predicts, and we did not test them.
Dropping the failure-chain counts. This is the bug from the start of the lesson. A version of the code above with the reverse pass removed gives:
he 0
she 1
his 0
hers 1
total 2The symptom is a count that is too small for any pattern that is a suffix of another pattern, here he inside she. The total is short by one. A random test against a brute force catches it at once, and a single hand-checked example such as ushers catches it too.
Using the trie without failure links. A trie that is only walked from the root finds a pattern only when the text starts exactly at its first letter. The symptom is zero matches for any pattern that begins in the middle of a longer match. The fix is the failure link.
Computing failure links in the wrong order. The failure link of a node needs the goto table of shallower nodes. Computing the links in depth-first order, or in any order that is not breadth first, reads a table entry before it is filled. The likely symptom is a wrong count on some inputs, with no crash. Use the BFS in the code above, and check that order lists the nodes from shallow to deep.
Letters outside the alphabet. The code uses c - 'a' as an index. An uppercase letter, a digit or a space gives an index outside 0 to 25, which is undefined behaviour in C++. The symptom can be a crash, or a silently wrong answer if the bad index happens to land inside the array. Read the statement's alphabet, and map other characters to their own alphabet before you call the code.
Forgetting the memory of the goto table. A dictionary with long patterns or many patterns can use far more memory than the statement suggests. The symptom is a "memory limit exceeded" verdict on a large test, with a correct answer on the small ones. Count the nodes before you choose the layout.
Empty patterns. An empty pattern matches at every position, and the statement must say how to count it. The code above does not handle it, so read the statement first and handle it on purpose.
Checklist
- Insert every pattern into the trie, and mark the end node of each pattern.
- Compute failure links in BFS order, starting from the root's children.
- Fill missing children with the goto of the failure link, so the text is one lookup per character.
- Count visits to each state while reading the text.
- Push the counts up the failure tree in reverse BFS order.
- Test on the
ushersexample and on 300 or more random small cases against a brute force. - Check the alphabet and the memory limit before you submit.
Here is a prompt to ask an AI assistant to review an Aho-Corasick implementation. A good answer names the lines it checked and gives a test input that would show each bug.
Review this Aho-Corasick implementation for counting pattern occurrences. Check:
(1) failure links are computed in breadth-first order and point to shallower nodes,
(2) missing goto entries are filled from the failure link,
(3) per-pattern counts include matches that are suffixes of longer matches,
(4) the alphabet and memory use are right for the statement.
For each problem, give a short input that exposes it. Do not change the code yet.
Say clearly what you ran and what you only read.Check the answer by running its inputs. A review that says "looks right" without a test input has not checked anything.
Summary
A trie stores a set of words by their prefixes, and Aho-Corasick adds failure links so that one pass over the text finds every occurrence of every word. The goto table turns each character into one lookup. Counts come from visits to each state, pushed up the failure tree. The main risk is quiet: a missing push of counts drops matches that are suffixes of other matches, and only a test with a known answer shows it. The checks in this lesson were the hand-worked example, 500 random cases against a brute force, and a timing run on a long text.
Practice problems
Each problem asks for a small program. Write your own tests first.
Problem 1: distinct words that occur. Input: a text, then a number m, then m words. A word may appear more than once in the list. Output: how many different words occur in the text at least once. Example: ushers with the words he, she, his, hers gives 3, since "his" does not occur. Hint: after the text pass, a word occurs if its end node was reached on the text or is on a failure chain of a reached node. Count each distinct end node only once.
Show the answer
Walk the text and mark every node that is on the failure chain of each state reached. A word occurs if its end node is marked. Count each end node once, so duplicate words in the input are not counted twice. Our run on the example printed 3. We checked this against a Python set of substrings on 300 random cases, with 0 mismatches.
Problem 2: the longest word ending at each position. Input: a text, then a dictionary as in Problem 1. Output: for each position in the text, the length of the longest dictionary word that ends there, or 0 if none does. Example: ushers gives 0 0 0 3 0 4, since "she" ends at position 3 and "hers" ends at position 5. Hint: store for each node the longest word that ends at it or on its failure chain. Compute this in BFS order, the same way the failure links are computed.
Show the answer
For each node, set bestLen to the larger of the word length ending at that node and the bestLen of its failure link. Compute it when the node is taken from the BFS queue, since the failure link is already set by then. Walking the text and printing bestLen of each state gives the answer. Our run on the example printed 0 0 0 3 0 4, and it matched a Python check on 300 random cases.
Problem 3: minimum XOR of two numbers. Input: a number n, then n numbers, each below 2^30. Output: the smallest value of a[i] XOR a[j] over all pairs with i not equal to j. Example: 3 10 5 25 2 8 gives 1, from 10 XOR 8 = 2 and 3 XOR 2 = 1. Hint: insert the numbers into a binary trie one by one. For each new number, walk the trie from the top bit down, and choose the child that matches its bit when one exists, since that makes the XOR bit 0.
Show the answer
Insert each number after querying it, so the query never matches itself. The query walks the trie from bit 30 down to bit 0. At each bit it prefers the child with the same bit, which keeps the XOR bit at 0, and it goes to the other child only when the same bit is missing. This is the code from our scratch program:
auto minXorWith = [&](unsigned x) -> unsigned {
int v = 0;
unsigned res = 0;
for (int b = 30; b >= 0; b--) {
int bit = (x >> b) & 1;
if (ch[v][bit] != -1) v = ch[v][bit];
else {
v = ch[v][bit ^ 1];
res |= 1u << b;
}
}
return res;
};Our run on the example printed 1. We checked the program against a brute force over all pairs on 300 random lists of 2 to 12 numbers from 0 to 1000, with 0 mismatches.