These are the notes for Competitive Programming episode 76. Aho-Corasick finds every occurrence of many patterns in a text in one pass. It is a trie of the patterns (episode 75) plus suffix links (KMP's fall back from episode 72, but able to land in any pattern), built with BFS. Missing edges are filled with direct jumps, which turns the trie into an automaton: one table lookup per letter of the text. Banned Words (count every occurrence of every word) shows the every-word-at-every-position brute force (TLE) and a real bug: without cnt[v] += cnt[link[v]], words hidden at the end of longer matches are missed (4 instead of 6). Word Report (how often each word occurs) pushes visit counts down the suffix links deepest first; in BFS order it gives 2 3 2 instead of 4 3 2. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.
The real-life hook
A building's keypad knows every flat's code. The slow way checks the keys you typed against each code, one by one. A smart panel stores all the codes in one tree, so codes that start the same share their first keys (the trie). After a key that doesn't continue, it doesn't start over: it keeps the longest ending of what you typed that is the start of any code (the suffix link). And a lamp lights for every code that ends at this key, including short codes hidden at the end of a longer one. Every key is read once.
Problem A1 · Banned Words
(Written for this course.)
- k banned words (total length ≤ 10^5) and a message t (|t| ≤ 2·10^6), all lowercase.
- Print the total number of occurrences of all banned words in t (overlapping occurrences count).
3
pan paneer neer
paneerpaneer
pan, paneer and neer each occur twice: 6.
Attempt 1: every word at every position (TLE)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int k;
cin >> k;
vector<string> words(k);
for (auto& w : words) cin >> w;
string t;
cin >> t;
ll total = 0;
for (int i = 0; i < (int)t.size(); i++) // every position
for (auto& w : words) // every word
if (t.compare(i, w.size(), w) == 0) total++;
cout << total << "\n";
}
3
pan paneer neer
paneerpaneer
6
Worst case: all 18,278 words of one to three letters, and two million as: about 3.7·10^10 checks.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
vector<string> words; // every word of 1 to 3 letters
for (char a = 'a'; a <= 'z'; a++) {
words.push_back(string{a});
for (char b = 'a'; b <= 'z'; b++) {
words.push_back(string{a, b});
for (char c = 'a'; c <= 'z'; c++) words.push_back(string{a, b, c});
}
}
string t(2000000, 'a'); // 18278 words, 2 million letters
ll total = 0;
for (int i = 0; i < (int)t.size(); i++) // every position
for (auto& w : words) // every word
if (t.compare(i, w.size(), w) == 0) total++;
cout << total << "\n";
}
Time Limit Exceeded
In the SyntaxPilot compiler this shows Time Limit Exceeded. Running KMP once per word is linear per word, but with thousands of words it is still thousands of passes over the message.
Suffix links
- Every trie node is a prefix of some word.
- link[v] = the node of the longest proper suffix of v that is also in the trie (the root if none).
paneer→neer,pane→ne,pan→n,pa→ root.- Build in BFS order (by depth), so a node's link is finished before its children need it: for the child u of v by letter c, link[u] = go[link[v]][c].
The automaton
- In KMP, a mismatch meant a
whileloop of fall backs. Here every missing edge is filled once:go[v][c] = go[link[v]][c](already final, by BFS order). - Scanning the text is then one lookup per letter:
v = go[v][c]. - Words can hide at the end of a longer match: when the walk stands at
paneer, the wordneeralso ends there. So each node counts the words ending at it plus those ending at its link:cnt[v] += cnt[link[v]](in BFS order, the link's count is already final).
words: pan, paneer, neer
trie: root ─ p ─ a ─ n* ─ e ─ e ─ r* (* = a word ends here)
└ n ─ e ─ e ─ r*
links: paneer → neer · panee → nee · pane → ne · pan → n · pa → root · p → root
neer → root · nee → root · ne → root · n → root
cnt: pan = 1, neer = 1, paneer = 1 + cnt[neer] = 2
The hidden-word bug
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct AhoCorasick {
vector<array<int, 26>> go; // trie edges, then direct jumps
vector<int> link, cnt, order; // suffix link, words ending here, BFS order
AhoCorasick() { go.push_back({}); link.push_back(0); cnt.push_back(0); }
int insert(const string& w) {
int v = 0;
for (char ch : w) {
int c = ch - 'a';
if (!go[v][c]) { go[v][c] = go.size(); go.push_back({}); link.push_back(0); cnt.push_back(0); }
v = go[v][c];
}
cnt[v]++; // a word ends here
return v;
}
void build() { // BFS from the root
queue<int> q;
for (int c = 0; c < 26; c++) if (go[0][c]) q.push(go[0][c]);
while (!q.empty()) {
int v = q.front(); q.pop();
order.push_back(v);
for (int c = 0; c < 26; c++) {
int u = go[v][c];
if (u) link[u] = go[link[v]][c], q.push(u); // fall back, like KMP
else go[v][c] = go[link[v]][c]; // a missing edge jumps straight there
}
}
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int k;
cin >> k;
vector<string> words(k);
for (auto& w : words) cin >> w;
string t;
cin >> t;
AhoCorasick ac;
for (auto& w : words) ac.insert(w);
ac.build();
ll total = 0;
int v = 0;
for (char ch : t) {
v = ac.go[v][ch - 'a']; // one step per letter
total += ac.cnt[v]; // every word ending here
}
cout << total << "\n";
}
3
pan paneer neer
paneerpaneer
4
Wrong: at the end of each paneer, only paneer is counted; neer ends there too.
The fix: add the link's count
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct AhoCorasick {
vector<array<int, 26>> go; // trie edges, then direct jumps
vector<int> link, cnt, order; // suffix link, words ending here, BFS order
AhoCorasick() { go.push_back({}); link.push_back(0); cnt.push_back(0); }
int insert(const string& w) {
int v = 0;
for (char ch : w) {
int c = ch - 'a';
if (!go[v][c]) { go[v][c] = go.size(); go.push_back({}); link.push_back(0); cnt.push_back(0); }
v = go[v][c];
}
cnt[v]++; // a word ends here
return v;
}
void build() { // BFS from the root
queue<int> q;
for (int c = 0; c < 26; c++) if (go[0][c]) q.push(go[0][c]);
while (!q.empty()) {
int v = q.front(); q.pop();
order.push_back(v);
cnt[v] += cnt[link[v]]; // words that end as a suffix here
for (int c = 0; c < 26; c++) {
int u = go[v][c];
if (u) link[u] = go[link[v]][c], q.push(u); // fall back, like KMP
else go[v][c] = go[link[v]][c]; // a missing edge jumps straight there
}
}
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int k;
cin >> k;
vector<string> words(k);
for (auto& w : words) cin >> w;
string t;
cin >> t;
AhoCorasick ac;
for (auto& w : words) ac.insert(w);
ac.build();
ll total = 0;
int v = 0;
for (char ch : t) {
v = ac.go[v][ch - 'a']; // one step per letter
total += ac.cnt[v]; // every word ending here
}
cout << total << "\n";
}
3
pan paneer neer
paneerpaneer
6
A message with no banned word:
2
chai lassi
tea
0
The worst case (note the long long: the number of matches can be far bigger than the message):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct AhoCorasick {
vector<array<int, 26>> go; // trie edges, then direct jumps
vector<int> link, cnt, order; // suffix link, words ending here, BFS order
AhoCorasick() { go.push_back({}); link.push_back(0); cnt.push_back(0); }
int insert(const string& w) {
int v = 0;
for (char ch : w) {
int c = ch - 'a';
if (!go[v][c]) { go[v][c] = go.size(); go.push_back({}); link.push_back(0); cnt.push_back(0); }
v = go[v][c];
}
cnt[v]++; // a word ends here
return v;
}
void build() { // BFS from the root
queue<int> q;
for (int c = 0; c < 26; c++) if (go[0][c]) q.push(go[0][c]);
while (!q.empty()) {
int v = q.front(); q.pop();
order.push_back(v);
cnt[v] += cnt[link[v]]; // words that end as a suffix here
for (int c = 0; c < 26; c++) {
int u = go[v][c];
if (u) link[u] = go[link[v]][c], q.push(u); // fall back, like KMP
else go[v][c] = go[link[v]][c]; // a missing edge jumps straight there
}
}
}
};
int main() {
vector<string> words; // every word of 1 to 3 letters
for (char a = 'a'; a <= 'z'; a++) {
words.push_back(string{a});
for (char b = 'a'; b <= 'z'; b++) {
words.push_back(string{a, b});
for (char c = 'a'; c <= 'z'; c++) words.push_back(string{a, b, c});
}
}
string t(2000000, 'a'); // 18278 words, 2 million letters
AhoCorasick ac;
for (auto& w : words) ac.insert(w);
ac.build();
ll total = 0;
int v = 0;
for (char ch : t) {
v = ac.go[v][ch - 'a']; // one step per letter
total += ac.cnt[v]; // every word ending here
}
cout << total << "\n";
}
5999997
Stress test
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct AhoCorasick {
vector<array<int, 26>> go; // trie edges, then direct jumps
vector<int> link, cnt, order; // suffix link, words ending here, BFS order
AhoCorasick() { go.push_back({}); link.push_back(0); cnt.push_back(0); }
int insert(const string& w) {
int v = 0;
for (char ch : w) {
int c = ch - 'a';
if (!go[v][c]) { go[v][c] = go.size(); go.push_back({}); link.push_back(0); cnt.push_back(0); }
v = go[v][c];
}
cnt[v]++; // a word ends here
return v;
}
void build() { // BFS from the root
queue<int> q;
for (int c = 0; c < 26; c++) if (go[0][c]) q.push(go[0][c]);
while (!q.empty()) {
int v = q.front(); q.pop();
order.push_back(v);
cnt[v] += cnt[link[v]]; // words that end as a suffix here
for (int c = 0; c < 26; c++) {
int u = go[v][c];
if (u) link[u] = go[link[v]][c], q.push(u); // fall back, like KMP
else go[v][c] = go[link[v]][c]; // a missing edge jumps straight there
}
}
}
};
int main() {
mt19937 gen(76);
for (int it = 1; it <= 500; it++) {
int k = gen() % 5 + 1;
vector<string> words(k);
AhoCorasick ac;
for (auto& w : words) {
w = string(gen() % 4 + 1, 'a');
for (char& c : w) c = 'a' + gen() % 2;
ac.insert(w);
}
ac.build();
string t(gen() % 20 + 1, 'a');
for (char& c : t) c = 'a' + gen() % 2;
ll slow = 0, fast = 0;
for (int i = 0; i < (int)t.size(); i++)
for (auto& w : words) if (t.compare(i, w.size(), w) == 0) slow++;
int v = 0;
for (char ch : t) v = ac.go[v][ch - 'a'], fast += ac.cnt[v];
if (slow != fast) { cout << "mismatch on test " << it; return 0; }
}
cout << "all 500 tests passed";
}
all 500 tests passed
Problem A2 · Word Report
(Written for this course.)
- Same input; print how often each banned word occurs.
3
a aa aaa
aaaa
a → 4, aa → 3, aaa → 2: 4 3 2.
Observation. Walk the message and only mark seen[v]++ where the walk stands after each letter. Every time the walk stood at v, the text there also ends with link[v], so every visit of v is also a visit of link[v]: seen[link[v]] += seen[v]. A node must collect all its counts before passing them on, and its "children" along the links are deeper, so go deepest first: the BFS order reversed.
The BFS-order bug
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct AhoCorasick {
vector<array<int, 26>> go; // trie edges, then direct jumps
vector<int> link, cnt, order; // suffix link, words ending here, BFS order
AhoCorasick() { go.push_back({}); link.push_back(0); cnt.push_back(0); }
int insert(const string& w) {
int v = 0;
for (char ch : w) {
int c = ch - 'a';
if (!go[v][c]) { go[v][c] = go.size(); go.push_back({}); link.push_back(0); cnt.push_back(0); }
v = go[v][c];
}
cnt[v]++; // a word ends here
return v;
}
void build() { // BFS from the root
queue<int> q;
for (int c = 0; c < 26; c++) if (go[0][c]) q.push(go[0][c]);
while (!q.empty()) {
int v = q.front(); q.pop();
order.push_back(v);
cnt[v] += cnt[link[v]]; // words that end as a suffix here
for (int c = 0; c < 26; c++) {
int u = go[v][c];
if (u) link[u] = go[link[v]][c], q.push(u); // fall back, like KMP
else go[v][c] = go[link[v]][c]; // a missing edge jumps straight there
}
}
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int k;
cin >> k;
vector<string> words(k);
for (auto& w : words) cin >> w;
string t;
cin >> t;
AhoCorasick ac;
vector<int> ends;
for (auto& w : words) ends.push_back(ac.insert(w));
ac.build();
vector<ll> seen(ac.go.size());
int v = 0;
for (char ch : t) v = ac.go[v][ch - 'a'], seen[v]++; // where the walk stands
for (int i = 0; i < (int)ac.order.size(); i++) { // in BFS order
int u = ac.order[i];
seen[ac.link[u]] += seen[u]; // pass the count to the suffix
}
for (int e : ends) cout << seen[e] << " ";
cout << "\n";
}
3
a aa aaa
aaaa
2 3 2
The node a passed on its count before it received the counts from aa.
The fix: deepest first
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct AhoCorasick {
vector<array<int, 26>> go; // trie edges, then direct jumps
vector<int> link, cnt, order; // suffix link, words ending here, BFS order
AhoCorasick() { go.push_back({}); link.push_back(0); cnt.push_back(0); }
int insert(const string& w) {
int v = 0;
for (char ch : w) {
int c = ch - 'a';
if (!go[v][c]) { go[v][c] = go.size(); go.push_back({}); link.push_back(0); cnt.push_back(0); }
v = go[v][c];
}
cnt[v]++; // a word ends here
return v;
}
void build() { // BFS from the root
queue<int> q;
for (int c = 0; c < 26; c++) if (go[0][c]) q.push(go[0][c]);
while (!q.empty()) {
int v = q.front(); q.pop();
order.push_back(v);
cnt[v] += cnt[link[v]]; // words that end as a suffix here
for (int c = 0; c < 26; c++) {
int u = go[v][c];
if (u) link[u] = go[link[v]][c], q.push(u); // fall back, like KMP
else go[v][c] = go[link[v]][c]; // a missing edge jumps straight there
}
}
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int k;
cin >> k;
vector<string> words(k);
for (auto& w : words) cin >> w;
string t;
cin >> t;
AhoCorasick ac;
vector<int> ends;
for (auto& w : words) ends.push_back(ac.insert(w));
ac.build();
vector<ll> seen(ac.go.size());
int v = 0;
for (char ch : t) v = ac.go[v][ch - 'a'], seen[v]++; // where the walk stands
for (int i = (int)ac.order.size() - 1; i >= 0; i--) { // deepest first
int u = ac.order[i];
seen[ac.link[u]] += seen[u]; // pass the count to the suffix
}
for (int e : ends) cout << seen[e] << " ";
cout << "\n";
}
3
a aa aaa
aaaa
4 3 2
3
pan paneer neer
paneerpaneer
2 2 2
Stress test
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct AhoCorasick {
vector<array<int, 26>> go; // trie edges, then direct jumps
vector<int> link, cnt, order; // suffix link, words ending here, BFS order
AhoCorasick() { go.push_back({}); link.push_back(0); cnt.push_back(0); }
int insert(const string& w) {
int v = 0;
for (char ch : w) {
int c = ch - 'a';
if (!go[v][c]) { go[v][c] = go.size(); go.push_back({}); link.push_back(0); cnt.push_back(0); }
v = go[v][c];
}
cnt[v]++; // a word ends here
return v;
}
void build() { // BFS from the root
queue<int> q;
for (int c = 0; c < 26; c++) if (go[0][c]) q.push(go[0][c]);
while (!q.empty()) {
int v = q.front(); q.pop();
order.push_back(v);
cnt[v] += cnt[link[v]]; // words that end as a suffix here
for (int c = 0; c < 26; c++) {
int u = go[v][c];
if (u) link[u] = go[link[v]][c], q.push(u); // fall back, like KMP
else go[v][c] = go[link[v]][c]; // a missing edge jumps straight there
}
}
}
};
int main() {
mt19937 gen(76);
for (int it = 1; it <= 500; it++) {
int k = gen() % 5 + 1;
vector<string> words(k);
AhoCorasick ac;
vector<int> ends;
for (auto& w : words) {
w = string(gen() % 4 + 1, 'a');
for (char& c : w) c = 'a' + gen() % 2;
ends.push_back(ac.insert(w));
}
ac.build();
string t(gen() % 20 + 1, 'a');
for (char& c : t) c = 'a' + gen() % 2;
vector<ll> seen(ac.go.size());
int v = 0;
for (char ch : t) v = ac.go[v][ch - 'a'], seen[v]++;
for (int i = (int)ac.order.size() - 1; i >= 0; i--) seen[ac.link[ac.order[i]]] += seen[ac.order[i]];
for (int j = 0; j < k; j++) {
ll slow = 0;
for (int i = 0; i < (int)t.size(); i++) if (t.compare(i, words[j].size(), words[j]) == 0) slow++;
if (slow != seen[ends[j]]) { cout << "mismatch on test " << it; return 0; }
}
}
cout << "all 500 tests passed";
}
all 500 tests passed
Complexity vs the constraints
| Method | Time | Verdict |
|---|---|---|
| every word at every position | O( | t |
| KMP once per word | O(k · | t |
| build the automaton | O(26 · nodes) ≈ 2.6·10^6 | fast |
| A1: walk the message | O( | t |
| A2: push counts | O(nodes) | accepted |
Memory: 26 ints per node, about 10 MB for 10^5 nodes.
Common mistakes (and the real outputs)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
no cnt[v] += cnt[link[v]] |
4 instead of 6 |
short words hide in longer ones | add the link's count during the BFS |
| pushing counts in BFS order | 2 3 2 instead of 4 3 2 |
a node passes on before it collects | reverse BFS order |
| building links with DFS | Wrong Answer | link[v] may not be final yet | BFS: shallow nodes first |
int for the number of matches |
overflow | matches can reach | t |
| setting the root's children's links to themselves | infinite loop / wrong jumps | depth-1 nodes link to the root | leave link = 0 for them |
keeping the KMP while loop |
correct but slower | the missing edges already jump | v = go[v][c] |
Mini project
Build a tiny chat filter: read banned words and a few messages, and print each message with every letter that belongs to a banned word replaced by * (for each position, store the longest word ending there, then mark backwards).
Practice
These are the homework problems from the episode.
1. The first position where any banned word ends. Walk the automaton and stop at the first node with cnt[v] > 0 (after adding link counts).
Solution (checked against brute force on 100 random tests)
#include <bits/stdc++.h>
using namespace std;
int main() { // the first position where any banned word ends
int k;
cin >> k;
vector<array<int, 26>> go(1);
vector<int> link(1, 0), cnt(1, 0);
for (int i = 0; i < k; i++) {
string w;
cin >> w;
int v = 0;
for (char ch : w) {
int c = ch - 'a';
if (!go[v][c]) { go[v][c] = go.size(); go.push_back({}); link.push_back(0); cnt.push_back(0); }
v = go[v][c];
}
cnt[v]++;
}
queue<int> q;
for (int c = 0; c < 26; c++) if (go[0][c]) q.push(go[0][c]);
while (!q.empty()) {
int v = q.front(); q.pop();
cnt[v] += cnt[link[v]];
for (int c = 0; c < 26; c++) {
int u = go[v][c];
if (u) link[u] = go[link[v]][c], q.push(u);
else go[v][c] = go[link[v]][c];
}
}
string t;
cin >> t;
int v = 0;
for (int i = 0; i < (int)t.size(); i++) {
v = go[v][t[i] - 'a'];
if (cnt[v]) { cout << i + 1 << "\n"; return 0; } // 1-indexed end position
}
cout << -1 << "\n"; // the message is clean
}
2
chai lassi
masalachai
10
2. Censor the message. For each node store len[v] = the longest word ending there (max with len[link[v]] in BFS order). Walking the text, a word of length L ends at i, so mark positions i − L + 1 .. i (use a difference array or a running "cover until" pointer).
Hint
Keep cover = max(cover, i) starting from i − L + 1 while scanning right to left, or add +1/−1 in a difference array and print * where the prefix sum is positive.
3. The longest banned word ending at each position. Exactly len[v] from exercise 2 at the node where the walk stands.
4. Count the strings of length L that contain no banned word. DP on the automaton: dp[step][v] = the number of ways to stand at node v; forbid nodes with cnt[v] > 0; each step tries all 26 letters via go[v][c]. O(L · nodes · 26).
Hint
Start with dp[0][root] = 1. The answer is the sum of dp[L][v] over allowed nodes, usually modulo 10^9 + 7.
Quick quiz
// banned words: abcd, bc, c
// the trie node for "abc"
// link["abc"] = ?
A) the node bc · B) the node c · C) the root · D) the node ab
Answer
A. The proper suffixes of abc are bc and c; both are trie nodes and the link takes the longest, bc. Since link[bc] = c, cnt[abc] = cnt[bc] = 2 (bc and c), so both words are counted when the walk reaches abc.
Interview questions
- What problem does Aho-Corasick solve? Finding all occurrences of many patterns in a text in O(total pattern length · alphabet + |text| + matches) or, counting only, O(|text|) after building.
- What is a suffix link? A pointer from a trie node to the node of its longest proper suffix that is also in the trie.
- Why build with BFS? A node's link is shallower than the node, so in BFS order it is already finished.
- How is it related to KMP? With a single pattern, the suffix links are exactly KMP's prefix-function fall backs.
- What are dictionary (output) links? Links that skip to the nearest suffix that is a complete word, used to list every match without walking all suffix links.
- How do you count each word's occurrences? Count where the walk stands, then push counts along suffix links from the deepest node to the shallowest.
- What is the automaton? The trie with every missing edge replaced by the edge of the suffix link, so each letter is one lookup.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Multiple pattern matching | Finding many patterns in one text | banned words in a chat |
| Aho-Corasick | A trie of patterns + suffix links, built by BFS | one pass over the text |
| Trie | One node per prefix (episode 75) | p → pa → pan |
| Proper suffix | A suffix shorter than the whole string | neer of paneer |
| Suffix link (failure link) | Node of the longest proper suffix in the trie | paneer → neer |
| BFS order | Nodes by depth, shallow first | root's children first |
Goto table go[v][c] |
The next node after letter c | trie edge or jump |
| Automaton | A state machine: one lookup per letter | the filled go table |
cnt[v] |
Words ending at v or at its suffixes | cnt[paneer] = 2 |
| Dictionary link | The nearest suffix that is a whole word | paneer → neer |
| Hidden match | A word ending inside a longer match | neer in paneer |
| Reverse BFS order | Deepest nodes first | pushing counts |
long long |
64-bit integer | millions of matches |
| Stress test | Fast vs brute force on many random inputs | all 500 tests passed |
| Suffix array | All suffixes, sorted (next episode) | — |
Summary
- Aho-Corasick = trie of the words + suffix links built by BFS (
link[u] = go[link[v]][c]) + missing edges as direct jumps. - Count all matches:
cnt[v] += cnt[link[v]]in BFS order, thenv = go[v][c]; total += cnt[v]per letter. - Count each word:
seen[v]++while walking, thenseen[link[v]] += seen[v]deepest first. - Linear in the words' total length (× 26) plus the text length.
Solutions in C++, Java and Python
Problem A1 · Banned Words
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct AhoCorasick {
vector<array<int, 26>> go; // trie edges, then direct jumps
vector<int> link, cnt, order; // suffix link, words ending here, BFS order
AhoCorasick() { go.push_back({}); link.push_back(0); cnt.push_back(0); }
int insert(const string& w) {
int v = 0;
for (char ch : w) {
int c = ch - 'a';
if (!go[v][c]) { go[v][c] = go.size(); go.push_back({}); link.push_back(0); cnt.push_back(0); }
v = go[v][c];
}
cnt[v]++; // a word ends here
return v;
}
void build() { // BFS from the root
queue<int> q;
for (int c = 0; c < 26; c++) if (go[0][c]) q.push(go[0][c]);
while (!q.empty()) {
int v = q.front(); q.pop();
order.push_back(v);
cnt[v] += cnt[link[v]]; // words that end as a suffix here
for (int c = 0; c < 26; c++) {
int u = go[v][c];
if (u) link[u] = go[link[v]][c], q.push(u); // fall back, like KMP
else go[v][c] = go[link[v]][c]; // a missing edge jumps straight there
}
}
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int k;
cin >> k;
vector<string> words(k);
for (auto& w : words) cin >> w;
string t;
cin >> t;
AhoCorasick ac;
for (auto& w : words) ac.insert(w);
ac.build();
ll total = 0;
int v = 0;
for (char ch : t) {
v = ac.go[v][ch - 'a']; // one step per letter
total += ac.cnt[v]; // every word ending here
}
cout << total << "\n";
}
Java (checked on the samples)
import java.io.*;
import java.util.*;
public class Main {
static int[][] go = new int[100_001][26]; // trie edges, then direct jumps
static int[] link = new int[100_001], cnt = new int[100_001];
static int nodes = 1; // node 0 is the root
static int insert(String w) {
int v = 0;
for (int i = 0; i < w.length(); i++) {
int c = w.charAt(i) - 'a';
if (go[v][c] == 0) go[v][c] = nodes++;
v = go[v][c];
}
cnt[v]++; // a word ends here
return v;
}
static int[] build() { // BFS from the root; returns the BFS order
int[] order = new int[nodes];
int head = 0, tail = 0;
for (int c = 0; c < 26; c++) if (go[0][c] != 0) order[tail++] = go[0][c];
while (head < tail) {
int v = order[head++];
cnt[v] += cnt[link[v]]; // words that end as a suffix here
for (int c = 0; c < 26; c++) {
int u = go[v][c];
if (u != 0) { link[u] = go[link[v]][c]; order[tail++] = u; } // fall back, like KMP
else go[v][c] = go[link[v]][c]; // a missing edge jumps straight there
}
}
return Arrays.copyOf(order, tail);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in = new StreamTokenizer(br);
in.nextToken(); int k = (int) in.nval;
for (int i = 0; i < k; i++) { in.nextToken(); insert(in.sval); }
in.nextToken(); String t = in.sval;
build();
long total = 0;
int v = 0;
for (int i = 0; i < t.length(); i++) {
v = go[v][t.charAt(i) - 'a']; // one step per letter
total += cnt[v]; // every word ending here
}
System.out.println(total);
}
}
Python
import sys
from collections import deque
def main():
data = sys.stdin.read().split()
k = int(data[0])
words, t = data[1:1 + k], data[1 + k]
go = [[0] * 26] # trie edges, then direct jumps
link, cnt = [0], [0]
for w in words:
v = 0
for ch in w:
c = ord(ch) - 97
if not go[v][c]:
go[v][c] = len(go)
go.append([0] * 26)
link.append(0)
cnt.append(0)
v = go[v][c]
cnt[v] += 1 # a word ends here
q = deque(u for u in go[0] if u) # BFS from the root
while q:
v = q.popleft()
cnt[v] += cnt[link[v]] # words that end as a suffix here
for c in range(26):
u = go[v][c]
if u:
link[u] = go[link[v]][c] # fall back, like KMP
q.append(u)
else:
go[v][c] = go[link[v]][c] # a missing edge jumps straight there
total = v = 0
for ch in t:
v = go[v][ord(ch) - 97]
total += cnt[v]
print(total)
main()
Problem A2 · Word Report
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct AhoCorasick {
vector<array<int, 26>> go; // trie edges, then direct jumps
vector<int> link, cnt, order; // suffix link, words ending here, BFS order
AhoCorasick() { go.push_back({}); link.push_back(0); cnt.push_back(0); }
int insert(const string& w) {
int v = 0;
for (char ch : w) {
int c = ch - 'a';
if (!go[v][c]) { go[v][c] = go.size(); go.push_back({}); link.push_back(0); cnt.push_back(0); }
v = go[v][c];
}
cnt[v]++; // a word ends here
return v;
}
void build() { // BFS from the root
queue<int> q;
for (int c = 0; c < 26; c++) if (go[0][c]) q.push(go[0][c]);
while (!q.empty()) {
int v = q.front(); q.pop();
order.push_back(v);
cnt[v] += cnt[link[v]]; // words that end as a suffix here
for (int c = 0; c < 26; c++) {
int u = go[v][c];
if (u) link[u] = go[link[v]][c], q.push(u); // fall back, like KMP
else go[v][c] = go[link[v]][c]; // a missing edge jumps straight there
}
}
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int k;
cin >> k;
vector<string> words(k);
for (auto& w : words) cin >> w;
string t;
cin >> t;
AhoCorasick ac;
vector<int> ends;
for (auto& w : words) ends.push_back(ac.insert(w));
ac.build();
vector<ll> seen(ac.go.size());
int v = 0;
for (char ch : t) v = ac.go[v][ch - 'a'], seen[v]++; // where the walk stands
for (int i = (int)ac.order.size() - 1; i >= 0; i--) { // deepest first
int u = ac.order[i];
seen[ac.link[u]] += seen[u]; // pass the count to the suffix
}
for (int e : ends) cout << seen[e] << " ";
cout << "\n";
}
Java (checked on the samples)
import java.io.*;
import java.util.*;
public class Main {
static int[][] go = new int[100_001][26];
static int[] link = new int[100_001];
static int nodes = 1;
static int insert(String w) {
int v = 0;
for (int i = 0; i < w.length(); i++) {
int c = w.charAt(i) - 'a';
if (go[v][c] == 0) go[v][c] = nodes++;
v = go[v][c];
}
return v;
}
static int[] build() {
int[] order = new int[nodes];
int head = 0, tail = 0;
for (int c = 0; c < 26; c++) if (go[0][c] != 0) order[tail++] = go[0][c];
while (head < tail) {
int v = order[head++];
for (int c = 0; c < 26; c++) {
int u = go[v][c];
if (u != 0) { link[u] = go[link[v]][c]; order[tail++] = u; }
else go[v][c] = go[link[v]][c];
}
}
return Arrays.copyOf(order, tail);
}
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken(); int k = (int) in.nval;
int[] ends = new int[k];
for (int i = 0; i < k; i++) { in.nextToken(); ends[i] = insert(in.sval); }
in.nextToken(); String t = in.sval;
int[] order = build();
long[] seen = new long[nodes];
int v = 0;
for (int i = 0; i < t.length(); i++) { v = go[v][t.charAt(i) - 'a']; seen[v]++; } // where the walk stands
for (int i = order.length - 1; i >= 0; i--) seen[link[order[i]]] += seen[order[i]]; // deepest first
StringBuilder out = new StringBuilder();
for (int e : ends) out.append(seen[e]).append(' ');
System.out.println(out.toString().trim());
}
}
Python
import sys
from collections import deque
def main():
data = sys.stdin.read().split()
k = int(data[0])
words, t = data[1:1 + k], data[1 + k]
go, link, ends = [[0] * 26], [0], []
for w in words:
v = 0
for ch in w:
c = ord(ch) - 97
if not go[v][c]:
go[v][c] = len(go)
go.append([0] * 26)
link.append(0)
v = go[v][c]
ends.append(v)
order, q = [], deque(u for u in go[0] if u)
while q:
v = q.popleft()
order.append(v)
for c in range(26):
u = go[v][c]
if u:
link[u] = go[link[v]][c]
q.append(u)
else:
go[v][c] = go[link[v]][c]
seen = [0] * len(go)
v = 0
for ch in t:
v = go[v][ord(ch) - 97]
seen[v] += 1 # where the walk stands
for v in reversed(order): # deepest first
seen[link[v]] += seen[v]
print(" ".join(str(seen[e]) for e in ends))
main()