SyntaxPilot
Courses/Competitive Programming/Lesson 76
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 76 of 90

Aho-Corasick

queued

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.

  • 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 while loop 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 word neer also 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.

#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

  1. 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.
  2. 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.
  3. Why build with BFS? A node's link is shallower than the node, so in BFS order it is already finished.
  4. How is it related to KMP? With a single pattern, the suffix links are exactly KMP's prefix-function fall backs.
  5. 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.
  6. 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.
  7. 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, then v = go[v][c]; total += cnt[v] per letter.
  • Count each word: seen[v]++ while walking, then seen[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()