Senior LevelData Structures & Algorithms
How does the Aho-Corasick Algorithm enable multi-pattern string matching?
ā Interview Prompt: Explain Aho-Corasick automaton, failure links (similar to KMP), O(N+M+K) multi-pattern search, and use cases.
Aho-Corasick extends a Trie with failure links (like KMP failure function) to match multiple patterns simultaneously in $O(N + M + K)$ where $N$ = text length, $M$ = total pattern length, $K$ = number of matches.
Construction: $O(M)$
1
Build Trie from all patterns.
2
BFS to compute failure links: each state's failure link points to the longest proper suffix that is also a prefix of some pattern.
3
Compute output links for chained pattern outputs.
Searching: $O(N + K)$
Walk the text through the automaton; follow failure links on mismatches (no backtracking in text!).
Code Implementation Example
typescript
class AhoCorasick {
goto: Map<string, number>[] = [new Map()];
fail: number[] = [0];
output: number[][] = [[]];
addPattern(pattern: string, id: number): void {
let state = 0;
for (const ch of pattern) {
if (!this.goto[state].has(ch)) {
this.goto[state].set(ch, this.goto.length);
this.goto.push(new Map());
this.output.push([]);
this.fail.push(0);
}
state = this.goto[state].get(ch)!;
}
this.output[state].push(id);
}
build(): void { // BFS to compute failure links
const queue: number[] = [];
for (const [, s] of this.goto[0]) { this.fail[s] = 0; queue.push(s); }
while (queue.length) {
const u = queue.shift()!;
for (const [ch, v] of this.goto[u]) {
let f = this.fail[u];
while (f && !this.goto[f].has(ch)) f = this.fail[f];
this.fail[v] = this.goto[f].get(ch) ?? 0;
if (this.fail[v] === v) this.fail[v] = 0;
this.output[v] = [...this.output[v], ...this.output[this.fail[v]]];
queue.push(v);
}
}
}
}š”Aho-Corasick automaton with failure links for O(N+M+K) multi-pattern search.
šÆ Interview Key Takeaway
Aho-Corasick reduces multi-pattern search from O(NĆP) (P = patterns Ć avg length) to O(N+M+K). Used in antivirus scanners, network intrusion detection, search engines.
#DSA#Aho-Corasick#String Matching#Advanced#Senior
Back to all Data Structures & Algorithms Questionsā