Aho-Corasick
A trie with failure links that searches many patterns in one text in a single pass.
Aho-Corasick
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Aho-Corasick is the multi-pattern string matcher for ``one text, many patterns.'' It starts from a trie of all patterns, then adds failure links so the scan never restarts from scratch after a mismatch.
When to Use It
Use it when:
there are many patterns,
the text is long enough that running KMP or naive search for each pattern separately is too slow,
shared pattern prefixes are significant.
Core Idea
Build a trie of the patterns. For each trie node, compute a failure link to the longest proper suffix of that node's string that is also a trie prefix. During text scanning:
follow the next trie edge when it exists,
otherwise follow failure links until a valid transition exists,
report all pattern endings attached to the reached state.
Key Insight
The failure link is the multi-pattern version of the KMP fallback. It preserves the longest suffix of the processed text that could still grow into some pattern. That is why already-checked characters are never rescanned.
Worked Problem
Problem.
You are given a dictionary of words and one long text. Count how many times each dictionary word appears in the text.
Why Aho-Corasick fits.
All patterns are queried against the same text. Their shared prefixes belong in one trie, and failure links prevent restarting from the root after every mismatch.
Scan view.
If the current state spells hers and the next character breaks that path, the automaton jumps by failure links to the longest suffix that is still a valid trie prefix, for example s or he, depending on the dictionary.
Correctness Intuition
At every position, the automaton state represents the longest suffix of the processed text that is also a trie prefix. Normal transitions extend that suffix; failure links shorten it to the next-best valid candidate. Therefore every pattern ending at the current position is exposed either directly in this state or through output information inherited from failure ancestors.
Complexity Analysis
If total pattern length is \(m\) and text length is \(n\), construction plus scanning is linear in \(m+n\) up to the chosen transition representation.
Implementation
The code uses a lowercase alphabet trie and supports:
pattern insertion,
failure-link construction,
text scanning that counts occurrences of every pattern.
Common Pitfalls
Forgetting to propagate output information along failure links.
Using a dense transition table on a huge alphabet and wasting memory.
Treating the automaton state as if it stored only one matched pattern.
Variants / Extensions
DP on the automaton for forbidden-substring problems.
Sparse transition maps for larger alphabets.
Counting total matches, distinct matches, or first/last occurrence positions.
Practice Problems
Count how many times each pattern appears in a long text.
Mark all positions where any forbidden pattern occurs.
DP on strings that must avoid a set of bad substrings.
References
Code
Contest-ready reference implementation for the idea explained above.
struct AhoCorasick {
struct Node {
array<int, 26> next{};
int link = 0;
vector<int> out;
Node() {
next.fill(-1);
}
};
vector<Node> trie;
AhoCorasick() : trie(1) {}
void add_pattern(const string& s, int id) {
int v = 0;
for (char ch : s) {
int c = ch - 'a';
if (trie[v].next[c] == -1) {
trie[v].next[c] = (int)trie.size();
trie.push_back(Node{});
}
v = trie[v].next[c];
}
trie[v].out.push_back(id);
}
void build() {
queue<int> q;
for (int c = 0; c < 26; ++c) {
int to = trie[0].next[c];
if (to == -1) {
trie[0].next[c] = 0;
} else {
trie[to].link = 0;
q.push(to);
}
}
while (!q.empty()) {
int v = q.front();
q.pop();
int link = trie[v].link;
for (int id : trie[link].out) {
trie[v].out.push_back(id);
}
for (int c = 0; c < 26; ++c) {
int to = trie[v].next[c];
if (to == -1) {
trie[v].next[c] = trie[link].next[c];
} else {
trie[to].link = trie[link].next[c];
q.push(to);
}
}
}
}
vector<int> match_counts(const string& text, int pattern_count) const {
vector<int> cnt(pattern_count, 0);
int v = 0;
for (char ch : text) {
int c = ch - 'a';
v = trie[v].next[c];
for (int id : trie[v].out) {
++cnt[id];
}
}
return cnt;
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.