Aho-Corasick Automaton

Build a trie of patterns, add failure links by BFS, and report overlapping matches during one text scan.

Core idea

Store all patterns in one trie. Failure links connect each state to its longest suffix that is also a trie prefix, so a mismatch reuses text already read instead of restarting every pattern.

Read the visualization

Solid edges form the trie and dashed edges show failures. The active automaton state follows each text character, and output links report overlapping pattern endings.

Insert the next pattern through shared trie-prefix edges.

1function ahoCorasick(patterns: string[], text: string): [number, number][] {
const next: Record<string, number>[] = [{}];   //  state  0 = root
const out: number[][] = [[]]; const fail = [0];
for (let pi = 0; pi < patterns.length; pi++) {  // insert Trie: insert pattern  insert 
  let s = 0;
  for (const c of patterns[pi]) {
    if (next[s][c] === undefined) { next.push({}); out.push([]); fail.push(0); next[s][c] = next.length - 1; }
    s = next[s][c];
  }
  out[s].push(pi);                              //  pattern insert point 
}
const q: number[] = [];
for (const c in next[0]) q.push(next[0][c]);    // BFS  start  point: root fail child  fail=root
while (q.length) {
  const u = q.shift()!;
  for (const c in next[u]) {                    // BFS fail fail
    const v = next[u][c]; q.push(v);
    let f = fail[u];
    while (f && next[f][c] === undefined) f = fail[f]; // fail parent fail fail fail c fail
    fail[v] = next[f][c] !== undefined && next[f][c] !== v ? next[f][c]: 0;
    out[v] = out[v].concat(out[fail[v]]);       //  output fail merge 
  }
}
const hits: [number, number][] = []; let s = 0;
for (let i = 0; i < text.length; i++) {
  while (s && next[s][text[i]] === undefined) s = fail[s]; // match fail match
  s = next[s][text[i]] ?? 0;
  for (const pi of out[s]) hits.push([pi, i]);  // hit hit (hit output hit duplicate hit)
}
return hits;
31}

pattern set: {he, she, hers}
text: ushers
built state: 3 / 8

Complexity and tradeoffs

Time: O(P+n+z). Space: O(P × alphabet) dense. P is total pattern length and z is output count; sparse transitions reduce memory.

Invariant: After consuming text position i, the active state represents the longest suffix of the processed text that is also a pattern prefix.

Where it fits

Aho-Corasick powers dictionary scanning, moderation filters, intrusion signatures, and lexing when many patterns must be found in the same stream.