Aho-Corasick
O(total pattern length + text)Match many patterns against one text simultaneously: a trie of the patterns with suffix links, compressed into an automaton where every node has a transition for every letter. Scan the text once; cnt at the current node counts patterns ending at that position.
// use it on
CSES: Counting Patterns ↗
Count how many times each pattern occurs in the text. Store pattern ids at their trie nodes and aggregate along suffix links.
// the code
struct AhoCorasick { // lowercase a-z
vector<array<int, 26>> next;
vector<int> link, cnt;
AhoCorasick() : next(1), link(1, 0), cnt(1, 0) { next[0].fill(0); }
int add(const string& s) { // returns the node of this word
int v = 0;
for (char ch : s) {
int c = ch - 'a';
if (next[v][c] == 0) {
next[v][c] = next.size();
next.push_back({});
next.back().fill(0);
link.push_back(0);
cnt.push_back(0);
}
v = next[v][c];
}
cnt[v]++;
return v;
}
void build() { // BFS: suffix links + automaton transitions
queue<int> q;
for (int c = 0; c < 26; c++)
if (next[0][c]) q.push(next[0][c]);
while (!q.empty()) {
int v = q.front();
q.pop();
cnt[v] += cnt[link[v]]; // aggregate along suffix links
for (int c = 0; c < 26; c++) {
int u = next[v][c];
if (!u) {
next[v][c] = next[link[v]][c];
} else {
link[u] = next[link[v]][c];
q.push(u);
}
}
}
}
// scan: v = next[v][ch - 'a'] per char; cnt[v] = matches ending here
};