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.
TypeScript Python Go Rust
1 function ahoCorasick ( patterns : string [], text : string ) : [ number , number ][] {
2 const next : Record < string , number >[] = [{}]; // state 0 = root
3 const out : number [][] = [[]]; const fail = [ 0 ];
4 for ( let pi = 0 ; pi < patterns. length ; pi ++ ) { // insert Trie: insert pattern insert
5 let s = 0 ;
6 for ( const c of patterns[pi]) {
7 if (next[s][c] === undefined ) { next. push ({}); out. push ([]); fail. push ( 0 ); next[s][c] = next. length - 1 ; }
8 s = next[s][c];
9 }
10 out[s]. push (pi); // pattern insert point
11 }
12 const q : number [] = [];
13 for ( const c in next[ 0 ]) q. push (next[ 0 ][c]); // BFS start point: root fail child fail=root
14 while (q. length ) {
15 const u = q. shift () ! ;
16 for ( const c in next[u]) { // BFS fail fail
17 const v = next[u][c]; q. push (v);
18 let f = fail[u];
19 while (f && next[f][c] === undefined ) f = fail[f]; // fail parent fail fail fail c fail
20 fail[v] = next[f][c] !== undefined && next[f][c] !== v ? next[f][c] : 0 ;
21 out[v] = out[v]. concat (out[fail[v]]); // output fail merge
22 }
23 }
24 const hits : [ number , number ][] = []; let s = 0 ;
25 for ( let i = 0 ; i < text. length ; i ++ ) {
26 while (s && next[s][text[i]] === undefined ) s = fail[s]; // match fail match
27 s = next[s][text[i]] ?? 0 ;
28 for ( const pi of out[s]) hits. push ([pi, i]); // hit hit (hit output hit duplicate hit)
29 }
30 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.
