Pattern Guide
Aho-Corasick Automaton
"Multi-pattern string matching in O(n + m + k). KMP generalized to many patterns."
Aho-Corasick is a trie augmented with failure links and output links, enabling simultaneous search for all patterns in a text in O(n + m + k) where n is text length, m is total pattern length, and k is total matches. It generalizes KMP to multiple patterns. Used in intrusion detection, DNA matching, and word filter problems.
Problems you can solve with this pattern
4 problems · click any to start solving
class AhoCorasick {
constructor() {
this.next = [new Array(26).fill(0)]; // node 0 = root
this.fail = [0];
this.output = [[]]; // patterns ending at this node
this.nodeCount = 1;
}
insert(pattern, id) {
let node = 0;
for (const ch of pattern) {
const c = ch.charCodeAt(0) - 97;
if (!this.next[node][c]) {
this.next.push(new Array(26).fill(0));
this.fail.push(0);
this.output.push([]);
this.next[node][c] = this.nodeCount++;
}
node = this.next[node][c];
}
this.output[node].push(id);
}
build() {
const queue = [];
for (let c = 0; c < 26; c++) {
if (this.next[0][c]) queue.push(this.next[0][c]);
// Root's children with no edge loop back to root (already 0)
}
let i = 0;
while (i < queue.length) {
const u = queue[i++];
this.output[u] = [...this.output[u], ...this.output[this.fail[u]]]; // inherit outputs
for (let c = 0; c < 26; c++) {
if (this.next[u][c]) {
this.fail[this.next[u][c]] = this.next[this.fail[u]][c];
queue.push(this.next[u][c]);
} else {
this.next[u][c] = this.next[this.fail[u]][c]; // shortcut
}
}
}
}
search(text) {
const results = []; // [{pos, patternId}]
let node = 0;
for (let i = 0; i < text.length; i++) {
const c = text.charCodeAt(i) - 97;
node = this.next[node][c];
for (const id of this.output[node]) results.push({pos: i, id});
}
return results;
}
}Aho-Corasick works in two phases. Build phase: (1) Insert all patterns into a trie, (2) Compute failure links via BFS — fail[node] = longest proper suffix of the string at node that is also a prefix of some pattern. Search phase: process text character by character, following trie edges or failure links. Each state maintains output links to collect all patterns ending at this position.
class AhoCorasick {
constructor() {
this.next = [new Array(26).fill(0)]; // node 0 = root
this.fail = [0];
this.output = [[]]; // patterns ending at this node
this.nodeCount = 1;
}
insert(pattern, id) {
let node = 0;
for (const ch of pattern) {
const c = ch.charCodeAt(0) - 97;
if (!this.next[node][c]) {
this.next.push(new Array(26).fill(0));
this.fail.push(0);
this.output.push([]);
this.next[node][c] = this.nodeCount++;
}
node = this.next[node][c];
}
this.output[node].push(id);
}
build() {
const queue = [];
for (let c = 0; c < 26; c++) {
if (this.next[0][c]) queue.push(this.next[0][c]);
// Root's children with no edge loop back to root (already 0)
}
let i = 0;
while (i < queue.length) {
const u = queue[i++];
this.output[u] = [...this.output[u], ...this.output[this.fail[u]]]; // inherit outputs
for (let c = 0; c < 26; c++) {
if (this.next[u][c]) {
this.fail[this.next[u][c]] = this.next[this.fail[u]][c];
queue.push(this.next[u][c]);
} else {
this.next[u][c] = this.next[this.fail[u]][c]; // shortcut
}
}
}
}
search(text) {
const results = []; // [{pos, patternId}]
let node = 0;
for (let i = 0; i < text.length; i++) {
const c = text.charCodeAt(i) - 97;
node = this.next[node][c];
for (const id of this.output[node]) results.push({pos: i, id});
}
return results;
}
}- KMP: single pattern, O(n + m)
- Rabin-Karp: multiple patterns, O(n + m) average with hashing
- Aho-Corasick: multiple patterns, O(n + Σm + k) guaranteed
Failure link construction: BFS level by level. For node u with parent p via character c: fail[u] = next[fail[p]][c] (follow parent's fail then same character).
Output propagation: output[u] = patterns ending exactly at u PLUS output[fail[u]] (patterns that are proper suffixes of current string).
Applications: spam/virus detection, DNA sequence matching, word censoring, competitive programming dictionary matching problems.