1. One-Liner
Aho–Corasick is a finite automaton built from a trie of patterns plus failure links (like KMP on steroids) so every text character is processed once.
2. The Problem It Solves
Find all occurrences of many patterns in one pass over T — intrusion detection, virus scanning, forbidden-word filters.
3. The Core Idea
Extend trie edges with suffix links: when no child matches, follow failure to the longest proper suffix that is a trie prefix — same spirit as KMP’s LPS but for a trie.
4. How It Works (Table)
| Step | What Happens |
|---|---|
| 1 | Insert all patterns into a trie; mark terminal outputs. |
| 2 | BFS to set failure link for each node (root fails to root). |
| 3 | Optionally add output links to aggregate dictionary suffix matches. |
| 4 | Walk T: follow goto or failure; emit matches at terminal/output chain. |
5. Dry Run Example
Patterns {he, she, his} on "ushers" — automaton transitions show overlapping hits without restarting.
6. Key Properties
| Property | Value | ||||
|---|---|---|---|---|---|
| Time | O(` | T | + matches + Σ | patterns | `) build + scan |
| Space | O(alphabet × nodes) typical |
7. Where It Is Used
| Domain | Use |
|---|---|
| Security | IDS signatures |
| Bioinformatics | Multiple motif scan |
| Search engines | Query dictionaries |
8. Interview Tips
Explain trie + BFS failure; relate failure to KMP border. Know memory vs Rabin–Karp batching tradeoffs.
9. Comparison with Other Algorithms
| Method | Multi-pattern |
|---|---|
| Repeat KMP | O(k·(n+m)) |
| Aho–Corasick | Near linear single pass |
| Rabin–Karp | Hash sets of patterns |
10. Complexity
| Metric | Value | ||
|---|---|---|---|
| Build | O(sum of pattern lengths × alphabet) typical | ||
| Search | O(` | T | + z) where z` = output size |
Implementation Example (PYTHON)
from collections import deque, defaultdict
class AhoCorasick:
def __init__(self, words):
self.next = []
self.link = []
self.out = []
self._new()
for w in words:
self._add(w)
self._build()
def _new(self):
self.next.append(defaultdict(int))
self.link.append(0)
self.out.append([])
def _add(self, w):
v = 0
for ch in w:
if ch not in self.next[v]:
self._new(); self.next[v][ch] = len(self.next) - 1
v = self.next[v][ch]
self.out[v].append(w)
def _build(self):
q = deque()
for ch, u in self.next[0].items():
self.link[u] = 0; q.append(u)
while q:
v = q.popleft()
for ch, u in self.next[v].items():
q.append(u); j = self.link[v]
while j and ch not in self.next[j]: j = self.link[j]
self.link[u] = self.next[j][ch] if ch in self.next[j] else 0
self.out[u].extend(self.out[self.link[u]])
def search(self, text):
v, hits = 0, []
for i, ch in enumerate(text):
while v and ch not in self.next[v]: v = self.link[v]
v = self.next[v][ch] if ch in self.next[v] else 0
for w in self.out[v]: hits.append((i - len(w) + 1, w))
return hits