Aho–Corasick (Multi-Pattern Matching)
Why this exists
You have a list of words and a long text, and you want to know where every word appears. A chat service blocks a few thousand banned words in every message. A network intrusion-detection system checks every packet against tens of thousands of attack signatures. A biologist looks for a few hundred short DNA motifs in a genome of billions of letters. An editor highlights every keyword of a programming language as you type.
With one pattern, you already know the answer: KMP or the Z-algorithm scans the text once, in time proportional to text plus pattern. With patterns, the obvious move is to run KMP times. That reads the text times. For 10,000 signatures and a gigabit of traffic per second, that is 10,000 gigabits of reading per second. It does not work.
Aho–Corasick reads the text once, however many patterns there are, and reports every occurrence of every pattern. Its running time is
where is the text length, is the total length of all patterns, and is the number of matches reported. You cannot do better: you must read the text, read the patterns, and write down the answer.
Alfred Aho and Margaret Corasick published it in 1975 ("Efficient string matching: an aid to bibliographic search", Communications of the ACM 18(6)). They built it at Bell Labs to speed up searching bibliographic records for lists of keywords. Aho later used the same idea in the original Unix fgrep ("fixed grep"), which searches a file for any of a list of fixed strings. Half a century later it still runs inside antivirus engines, network firewalls, search tools and bioinformatics pipelines.
This lesson builds the algorithm in three layers — a trie, failure links and output links — traces each layer by hand on four tiny words, proves it correct in plain words, and implements it in Python, Java, C++ and TypeScript.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "find all occurrences of any of these words / patterns / keywords" | Aho–Corasick over the word list |
| "a dictionary of banned / forbidden / special strings" and a long text | Aho–Corasick; react at each text position |
| "stream of characters: after each one, does some word end here?" | Aho–Corasick state kept between queries |
| "count how many times each pattern occurs" | Aho–Corasick + summing counts up the failure tree |
| "the text must not contain any of these strings", count/construct such texts | DP over Aho–Corasick states (states = "how much of a bad word I am in the middle of") |
| "longest substring avoiding all forbidden words" | Aho–Corasick + shortest forbidden suffix per state + sliding left end |
| "number of strings of length (huge) avoiding / maximizing patterns" | Aho–Corasick automaton + matrix exponentiation |
| A single pattern | KMP or Z — Aho–Corasick with one pattern is KMP |
| Patterns are all the same length | Rolling hash with a set of pattern hashes also works (Rabin–Karp) |
| Patterns are given after the text, many queries on one fixed text | Index the text instead: suffix array or suffix automaton |
| Patterns contain wildcards, character classes, repetition | A regex engine (Aho–Corasick is often its literal-prefilter) |
The meta-trigger: one text, many fixed patterns, all known in advance. If the patterns come first and the text streams by, build an automaton from the patterns. If the text comes first and patterns stream by, build an index of the text.
Intuition & first principles
The analogy: one security scanner, not one guard per item
Picture an airport. You could hire one guard per forbidden item: one checks every bag for knives, another checks every bag for lighters, another for liquids. Every bag is opened once per guard. Or you build one X-ray scanner that knows all the forbidden shapes at once, and every bag passes through it a single time. Aho–Corasick is that scanner. The bag is the text. The forbidden shapes are the patterns. The scanner is a small machine (an automaton) built once from the patterns.
A tiny example to hold in your head
Patterns: he, she, his, hers. Text: ushers (6 letters).
By eye: she starts at index 1 (u[she]rs), he starts at index 2 (us[he]rs), hers starts at index 2 (us[hers]). his does not appear. Three matches. Notice two things:
- Matches overlap and nest.
hesits insidesheand insidehers. An algorithm that findssheand then jumps past it would misshe. - Patterns share beginnings.
heandhersboth start withhe;heandhisboth start withh. Checking them separately repeats work.
Three ideas, one per layer
Idea 1: share the beginnings — a trie. Put all patterns in a trie (a prefix tree). Every node is a prefix of at least one pattern. Walking the trie while reading text letters is like checking all patterns at once, as long as we keep matching.
Idea 2: on a mismatch, don't start over — failure links. Suppose we have read sh and are at the trie node for sh. Next letter is e: fine, we reach she. But suppose the next letter were i. There is no shi in the trie. A naive scanner would go back to the root and re-read from the next start position. But we know what we just read: sh. Its ending h is itself a prefix in the trie (the start of he and his). So we can jump to the node h and try i from there, reaching hi. That jump is a failure link: from each node, it points to the node for the longest proper suffix of this node's string that is also in the trie. ("Proper" means shorter than the whole string.) This is exactly KMP's question — how much of what I matched can I reuse? — asked about a whole trie instead of one pattern.
Idea 3: don't miss the patterns hiding inside — output links. When we reach she, we report she. But he also just ended, and it is a suffix of she. The failure link of she points to he, so walking the failure chain from the current node finds every pattern that ends here. Walking it blindly can be slow (most nodes on the chain may not end a pattern), so each node also gets an output link: a shortcut to the nearest node on its failure chain that does end a pattern.
That is the whole algorithm. Build a trie, add failure links, add output links, then read the text one letter at a time: follow a trie edge if one exists, otherwise follow failure links until one does (or you are at the root), and at every position report the patterns at the current node and along its output links.
Vocabulary
- Trie node / state — a node of the trie; it stands for the string spelled from the root to it. We say "node
she" for the node whose string isshe. - goto edge — a trie edge labelled with one character.
- Failure link
fail(v)— points to the node for the longest proper suffix ofv's string that is also a node. The root's failure link is the root. - Failure chain —
v, fail(v), fail(fail(v)), …, root. - Output link
out(v)— the nearest node strictly aftervon its failure chain that ends a pattern, or "none". - Terminal node — a node where at least one pattern ends.
Mechanics
flowchart LR
P["Patterns he, she, his, hers"] --> T["1. Insert into a trie"]
T --> F["2. BFS: failure links"]
F --> O["3. Output links"]
O --> S["4. Scan text once"]
S --> R["Report pattern, start"]
Step 1: build the trie
Insert each pattern character by character. Reuse an existing edge if there is one; otherwise create a new node. Mark the node where the pattern ends. Nodes get ids in creation order.
| Insert | Path walked | New nodes created | Pattern ends at |
|---|---|---|---|
he | root →h→ ? →e→ ? | 1 = h, 2 = he | node 2 |
she | root →s→ ? →h→ ? →e→ ? | 3 = s, 4 = sh, 5 = she | node 5 |
his | root →h→ 1 →i→ ? →s→ ? | 6 = hi, 7 = his | node 7 |
hers | root →h→ 1 →e→ 2 →r→ ? →s→ ? | 8 = her, 9 = hers | node 9 |
Ten nodes (root = 0). The trie has at most nodes, where is the total pattern length, because each character creates at most one node. Here and we created 9 nodes: he and hers share h, e; his shares h.
Step 2: failure links, by breadth-first search
Definition. For a node with string , is the node whose string is the longest proper suffix of that is also in the trie. Some examples, by eye:
sh: proper suffixes arehand the empty string.his in the trie. Sofail(sh) = h.she: proper suffixeshe,e, empty.heis in the trie. Sofail(she) = he.his: proper suffixesis,s, empty.isis not in the trie,sis. Sofail(his) = s.her: proper suffixeser,r, empty. None ofer,ris in the trie. Sofail(her) = root.
How to compute them fast. Take a node reached from its parent by character , so . Any suffix of that is in the trie, other than the empty one, looks like (some suffix of ) , and because tries are closed under prefixes, itself must be in the trie. So the candidates are: walk the failure chain of — fail(u), fail(fail(u)), … — and stop at the first node that has a child by . That child is fail(v). If you reach the root and it has no child by either, fail(v) is the root.
Note that this walk uses fail(u) and the failure links of nodes shallower than . Breadth-first search (BFS, from BFS in Depth) processes nodes in order of depth, so when we reach , every shallower failure link is already known. Depth-1 nodes are a special case: their only proper suffix is empty, so their failure link is the root.
BFS order here is 1, 3, 2, 6, 4, 8, 7, 5, 9 (depth 1: h, s; depth 2: he, hi, sh; depth 3: her, his, she; depth 4: hers). The table below was produced by the trace generator scripts/traces/aho_corasick.py.
| Step | Node | Parent, char | Start at fail(parent) | Walk | fail | out |
|---|---|---|---|---|---|---|
| 1 | 1 h | root, h | — (depth 1) | — | 0 root | none |
| 2 | 3 s | root, s | — (depth 1) | — | 0 root | none |
| 3 | 2 he | 1, e | root | root has no e child | 0 root | none |
| 4 | 6 hi | 1, i | root | root has no i child | 0 root | none |
| 5 | 4 sh | 3, h | root | root has an h child → 1 | 1 h | none |
| 6 | 8 her | 2, r | root | root has no r child | 0 root | none |
| 7 | 7 his | 6, s | root | root has an s child → 3 | 3 s | none |
| 8 | 5 she | 4, e | 1 h | node 1 has an e child → 2 | 2 he | 2 |
| 9 | 9 hers | 8, s | root | root has an s child → 3 | 3 s | none |
Here is the trie with every failure link drawn dashed. Terminal nodes have a ✓.
flowchart LR
n0(("0 root"))
n0 -->|h| n1["1: h"]
n1 -->|e| n2["2: he ✓"]
n2 -->|r| n8["8: her"]
n8 -->|s| n9["9: hers ✓"]
n1 -->|i| n6["6: hi"]
n6 -->|s| n7["7: his ✓"]
n0 -->|s| n3["3: s"]
n3 -->|h| n4["4: sh"]
n4 -->|e| n5["5: she ✓"]
n4 -.->|fail| n1
n5 -.->|fail| n2
n7 -.->|fail| n3
n9 -.->|fail| n3
n1 -.-> n0
n2 -.-> n0
n3 -.-> n0
n6 -.-> n0
n8 -.-> n0
n5 ==>|out| n2
Read it like this: solid arrows are "the next letter matches, go deeper"; dashed arrows are "the next letter does not match here, retreat to the longest ending you can still use"; the thick arrow from she to he is the only output link — reaching she also means he just ended.
The failure links form a tree
Every non-root node has exactly one failure link, and it points to a strictly shallower node. So the failure links form a tree rooted at the root — the failure tree (also called the suffix-link tree of the dictionary). Many advanced problems become "do something on the failure tree": sum counts from leaves to the root, run an Euler tour and a Fenwick tree, and so on. You will meet it in the practice ladder.
Step 3: output links
When the scanner stands at node , the patterns that end at the current text position are exactly the terminal nodes on 's failure chain (we prove this below). The failure chain can be long while only a few of its nodes are terminal. The output link skips the non-terminal ones:
with $\text{out}(\text{root}) = $ none. Like fail, it only depends on a shallower node, so it is computed in the same BFS, right after fail(v). In the example only out(she) = he exists. To report at node : report the patterns ending at itself (if any), then jump to out(v), report, jump again, until none.
Why not just store, at each node, the full list of patterns that end there or anywhere on its chain? Because those lists can be huge: for the patterns a, aa, aaa, …, , the node would store patterns, would store , and the total is memory for — fine here, but with other dictionaries the copied lists blow up beyond . Output links cost one integer per node and give each reported match in .
Step 4: scan the text
Keep one variable, state, starting at the root. For each text character at index :
- While
stateis not the root and has no child by :state = fail(state). - If
statehas a child by , move to it; otherwise stay at the root. - Report every pattern at
stateand along its output links. A pattern found at index starts at .
SEARCH(text):
state = root
for i, c in enumerate(text):
while state != root and c not in goto[state]:
state = fail[state]
state = goto[state][c] if c in goto[state] else root
k = state
while k != none:
for p in patterns ending at k: report (p, i - len(p) + 1)
k = out[k]
Trace: scanning ushers
| char | state before | failure moves | state after | its string | reported | |
|---|---|---|---|---|---|---|
| 0 | u | 0 root | — | 0 root | (empty) | — |
| 1 | s | 0 | — | 3 | s | — |
| 2 | h | 3 | — | 4 | sh | — |
| 3 | e | 4 | — | 5 | she | she at 1; out → 2: he at 2 |
| 4 | r | 5 | 5 → 2 (she has no r) | 8 | her | — |
| 5 | s | 8 | — | 9 | hers | hers at 2 |
Look at row 4. We had matched she. The next letter r breaks it. KMP-style reuse: the longest ending of she that is still useful is he, so we jump there and continue with her. We never re-read h or e. The text pointer only moves forward; the only thing that moves backward is the trie state, and it moves to a shallower node each time.
Step through the whole thing — trie, BFS over failure links, then the scan — in the visualizer. The dashed edges labelled fail are the non-root failure links (the rest point to the root); the side table shows the text position and the matches so far.
The automaton view: a complete DFA
The scanner above follows a variable number of failure links per character. You can precompute them away. For every node and every character of the alphabet, define
Computed in BFS order, each entry is one lookup. The result is a deterministic finite automaton (DFA): exactly one table lookup per text character, no loops, no branches. This is the form used when the alphabet is small (DNA has 4 letters, bytes have 256) and speed matters more than memory, and it is the form you need for "DP over automaton states" problems.
Deeper: the DFA version in code (Python, alphabet ACGT)
from collections import deque
def build_dfa(patterns, alphabet="ACGT"):
idx = {c: i for i, c in enumerate(alphabet)}
A = len(alphabet)
nxt, fail, term = [[-1] * A], [0], [0]
for p in patterns:
u = 0
for c in p:
k = idx[c]
if nxt[u][k] == -1:
nxt.append([-1] * A)
fail.append(0)
term.append(0)
nxt[u][k] = len(nxt) - 1
u = nxt[u][k]
term[u] += 1
q = deque()
for k in range(A):
if nxt[0][k] == -1:
nxt[0][k] = 0
else:
q.append(nxt[0][k])
while q:
u = q.popleft()
term[u] += term[fail[u]] # fail[u] is shallower, so already final
for k in range(A):
v = nxt[u][k]
if v == -1:
nxt[u][k] = nxt[fail[u]][k] # missing edge: borrow the failure state's move
else:
fail[v] = nxt[fail[u]][k]
q.append(v)
return nxt, term, idx
def count_motif_hits(dna, motifs):
nxt, term, idx = build_dfa(motifs)
s = total = 0
for c in dna:
s = nxt[s][idx[c]] # exactly one table lookup per character
total += term[s]
return total
assert count_motif_hits("ACGTACGTTACG", ["ACG", "CG", "TTA"]) == 7
Two tricks hide in there. fail[v] = nxt[fail[u]][k] is the whole failure-chain walk in one lookup, because nxt[fail[u]] is already complete. And term[u] += term[fail[u]] turns "number of patterns ending at this node or anywhere on its chain" into one number per node, which is all a counting problem needs. This version was cross-checked against brute force on 1,500 random DNA strings.
The ladder: brute force → better → optimal
Problem: given patterns of total length (longest pattern ) and a text of length , report every occurrence of every pattern ( in total).
Rung 1: naive check of every pattern at every position
For each start position and each pattern, compare character by character. comparisons in the worst case (text aaaa…, patterns aaa…ab). Simple and fine for tiny inputs; the oracle you test against.
Rung 2: KMP once per pattern
Run KMP (or Z) separately for each pattern. Each run is , so the total is . Much better when patterns are long, but the text is still read times. With and that is steps.
Rung 3: rolling hash per distinct length
Group patterns by length. For each distinct length , slide a rolling hash of width over the text and look each window's hash up in a hash set of that group's pattern hashes. expected, where is the number of distinct lengths (at most , since lengths ). Great when all patterns have one length. Probabilistic unless you verify, and the factor still hurts.
Rung 4: trie walk from every start position
Insert all patterns into a trie. From every text position , walk the trie along text[i], text[i+1], … until the walk falls off, reporting terminal nodes. : one walk per position, each at most steps. This shares work between patterns but not between positions — the walk from re-reads what the walk from already read.
Rung 5: Aho–Corasick
Rung 4 plus failure links: instead of restarting at , jump to the longest suffix of what was read that is still a trie node. Plus output links so reporting costs per match. to build (times the cost of a child lookup), to scan. Optimal up to the cost of child lookups.
| Rung | Method | Time | Extra space | Why it improves |
|---|---|---|---|---|
| 1 | Naive, every pattern × every position | Baseline oracle | ||
| 2 | KMP per pattern | No re-reading within one pattern | ||
| 3 | Rolling hash per distinct length | expected | One pass per length, not per pattern | |
| 4 | Trie walk from every position | Shares prefixes between patterns | ||
| 5 | Aho–Corasick | map-based, table | Shares prefixes and reuses suffixes; one pass |
Correctness
The argument is the KMP argument with "pattern" replaced by "trie". It has three parts: what the state means, why failure links are right, and why reporting finds everything.
Lemma 1 (the failure chain lists every useful suffix)
For any node , the nodes on its failure chain are exactly the suffixes of that are trie nodes, in decreasing order of length.
In plain words: every ending of v's string that is still a beginning of some pattern shows up on the chain, longest first, and nothing else does.
Proof sketch. Each chain node is a suffix of the previous one, so all are suffixes of , and lengths strictly decrease. Could the chain skip one? Suppose is a suffix of that is a trie node, and the chain jumps from some (longer than ) to (shorter than ). But is a proper suffix of (both are suffixes of and is shorter) and is in the trie, so the longest such suffix, , is at least as long as . Contradiction.
Lemma 2 (failure links are computed correctly)
The BFS rule — walk 's chain from and take the first node with a -child — yields the longest proper suffix of in the trie.
Proof sketch. A non-empty proper suffix of in the trie has the form where is a proper suffix of , and is a trie node because tries contain all prefixes of their strings. By Lemma 1, the candidates are exactly the nodes on 's chain after , longest first. Taking the first that has a -child gives the longest . If none has one, the only remaining suffix is the empty string: the root. BFS guarantees the chain of (all shallower than ) is complete when is processed.
Invariant (what the state means)
After reading text[0..i], state is the node for the longest suffix of text[0..i] that is a trie node (the longest ending of what we have read that could still grow into a pattern).
Proof by induction. Before reading anything, the state is the root (the empty suffix). Suppose it holds after text[0..i-1] with state . Any suffix of text[0..i] that is a trie node is either empty or with a suffix of text[0..i-1] that is a trie node — and every such is a suffix of , because is the longest one. By Lemma 1 they are exactly the nodes on 's chain, longest first. The scan walks that chain and stops at the first node with a -child, which gives the longest ; if none exists, the root. That is the invariant for .
Theorem (every occurrence is reported exactly once)
Pattern ends at index ⇔ is a suffix of text[0..i]. Since is a trie node and the state is the longest suffix that is a trie node, is a suffix of , hence (Lemma 1) on the state's failure chain. The output links visit exactly the terminal nodes of that chain, each once. Conversely, everything reported is a terminal node on the chain, hence a pattern that is a suffix of text[0..i], hence a real occurrence. ∎
Complexity
Build: child lookups. Inserting is one lookup per pattern character. For failure links, the cost is the total number of chain steps in the BFS. Fix one pattern and look at the nodes along its path, at depths . Moving one level down the path increases the depth of the failure link by at most 1 (Lemma 2: fail(v) is a child of some node on fail(u)'s chain), and every chain step decreases it by at least 1. Depth never goes below 0, so along this path the chain steps total at most . Every node lies on some pattern's path; charging each node to one such path, the total over all nodes is at most . Output links are each.
Search: child lookups. The same "depth bank account" argument, in plain words: each text character can make the state one level deeper (one deposit). Each failure move makes it at least one level shallower (a withdrawal). You cannot withdraw more than you deposited, so over the whole text there are at most failure moves — on average at most one per character, even though a single character can trigger many. Reporting follows one output link per reported match: .
The cost of one child lookup depends on how you store children:
| Child storage | Lookup | Memory | Notes |
|---|---|---|---|
| Hash map per node | expected | General alphabets (Unicode, tokens); used in the code below | |
Sorted array / std::map | Deterministic, compact | ||
| Dense array of size | Small alphabets; enables the full DFA (no failure loop at search time) | ||
| Double-array trie / bitmap-compressed rows | close to | What production engines do |
With 10,000 signatures of average length 20 over bytes (), the dense DFA has about states and entries — 200 MB at 4 bytes each. That is why intrusion-detection engines spend so much effort on compressed state tables.
can dominate. With patterns a, aa, aaa, aaaa and text , there are matches. In general can be as large as . If you only need counts per pattern, do not enumerate: add 1 to the counter of the current state at each position, then at the end push counts from each node to its failure link in reverse BFS order (children of the failure tree before parents). That is regardless of ; see the Counting Patterns solution below.
Space. nodes; per node a child structure, fail, out, and the pattern ids that end there.
Implementation
The patterns and texts from this page, plus two edge cases: the nested patterns a, aa, aaa in aaaa (9 matches), and a dictionary with a duplicate (ab twice) and a pattern that is a suffix of another (b). Each pattern's id list lives at its terminal node, so duplicates are reported separately. Matches come out in the order their last character is read. The Python version was also cross-checked against brute force on 3,000 random inputs.
from collections import deque
class AhoCorasick:
def __init__(self, patterns):
self.patterns = list(patterns)
self.goto = [{}] # goto[u][c] = child of node u by character c
self.fail = [0] # longest proper suffix of node u that is also a trie node
self.ends = [[]] # indices of patterns that end exactly at node u
self.out = [-1] # nearest node on the failure chain that ends a pattern (-1: none)
for idx, p in enumerate(self.patterns):
u = 0
for c in p:
if c not in self.goto[u]:
self.goto.append({})
self.fail.append(0)
self.ends.append([])
self.out.append(-1)
self.goto[u][c] = len(self.goto) - 1
u = self.goto[u][c]
self.ends[u].append(idx)
q = deque(self.goto[0].values()) # depth 1: failure link is the root
while q:
u = q.popleft()
for c, v in self.goto[u].items():
f = self.fail[u]
while f and c not in self.goto[f]:
f = self.fail[f]
self.fail[v] = self.goto[f].get(c, 0)
w = self.fail[v]
self.out[v] = w if self.ends[w] else self.out[w]
q.append(v)
def search(self, text):
"""All (pattern, start) occurrences, in the order their last character is read."""
res = []
s = 0
for i, c in enumerate(text):
while s and c not in self.goto[s]:
s = self.fail[s]
s = self.goto[s].get(c, 0)
k = s
while k != -1:
for idx in self.ends[k]:
p = self.patterns[idx]
res.append((p, i - len(p) + 1))
k = self.out[k]
return res
if __name__ == "__main__":
ac = AhoCorasick(["he", "she", "his", "hers"])
assert ac.fail == [0, 0, 0, 0, 1, 2, 0, 3, 0, 3]
assert ac.search("ushers") == [("she", 1), ("he", 2), ("hers", 2)]
assert len(AhoCorasick(["a", "aa", "aaa"]).search("aaaa")) == 9
assert AhoCorasick(["ab", "ab", "b"]).search("abab") == [
("ab", 0), ("ab", 0), ("b", 1), ("ab", 2), ("ab", 2), ("b", 3)]
assert AhoCorasick(["xyz"]).search("abc") == []
print("aho-corasick OK")
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class AhoCorasick {
record Match(String pattern, int start) {}
private final List<String> patterns;
private final List<Map<Character, Integer>> next = new ArrayList<>();
private final List<Integer> fail = new ArrayList<>();
private final List<List<Integer>> ends = new ArrayList<>();
private final List<Integer> out = new ArrayList<>();
AhoCorasick(List<String> patterns) {
this.patterns = patterns;
newNode();
for (int idx = 0; idx < patterns.size(); idx++) {
int u = 0;
for (char c : patterns.get(idx).toCharArray()) {
Integer v = next.get(u).get(c);
if (v == null) {
v = newNode();
next.get(u).put(c, v);
}
u = v;
}
ends.get(u).add(idx);
}
ArrayDeque<Integer> q = new ArrayDeque<>(next.get(0).values()); // depth 1: fail = root
while (!q.isEmpty()) {
int u = q.poll();
for (Map.Entry<Character, Integer> e : next.get(u).entrySet()) {
char c = e.getKey();
int v = e.getValue();
int f = fail.get(u);
while (f != 0 && !next.get(f).containsKey(c)) f = fail.get(f);
int w = next.get(f).getOrDefault(c, 0);
fail.set(v, w);
out.set(v, ends.get(w).isEmpty() ? out.get(w) : w);
q.add(v);
}
}
}
private int newNode() {
next.add(new HashMap<>());
fail.add(0);
ends.add(new ArrayList<>());
out.add(-1);
return next.size() - 1;
}
List<Match> search(String text) {
List<Match> res = new ArrayList<>();
int s = 0;
for (int i = 0; i < text.length(); i++) {
char c = text.charAt(i);
while (s != 0 && !next.get(s).containsKey(c)) s = fail.get(s);
s = next.get(s).getOrDefault(c, 0);
for (int k = s; k != -1; k = out.get(k)) {
for (int idx : ends.get(k)) {
String p = patterns.get(idx);
res.add(new Match(p, i - p.length() + 1));
}
}
}
return res;
}
static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }
public static void main(String[] args) {
AhoCorasick ac = new AhoCorasick(List.of("he", "she", "his", "hers"));
check(ac.fail.equals(List.of(0, 0, 0, 0, 1, 2, 0, 3, 0, 3)), "fail links");
check(ac.search("ushers").equals(List.of(new Match("she", 1), new Match("he", 2), new Match("hers", 2))), "ushers");
check(new AhoCorasick(List.of("a", "aa", "aaa")).search("aaaa").size() == 9, "aaaa");
check(new AhoCorasick(List.of("ab", "ab", "b")).search("abab").equals(List.of(
new Match("ab", 0), new Match("ab", 0), new Match("b", 1),
new Match("ab", 2), new Match("ab", 2), new Match("b", 3))), "duplicates");
check(new AhoCorasick(List.of("xyz")).search("abc").isEmpty(), "no match");
System.out.println("aho-corasick OK");
}
}
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <utility>
#include <vector>
class AhoCorasick {
public:
explicit AhoCorasick(const std::vector<std::string>& patterns) : patterns_(patterns) {
newNode();
for (int idx = 0; idx < (int)patterns_.size(); ++idx) {
int u = 0;
for (char c : patterns_[idx]) {
std::map<char, int>::iterator it = next_[u].find(c);
if (it == next_[u].end()) {
int v = newNode(); // may reallocate next_, so do not keep references
next_[u][c] = v;
u = v;
} else {
u = it->second;
}
}
ends_[u].push_back(idx);
}
std::queue<int> q;
for (const auto& kv : next_[0]) q.push(kv.second); // depth 1: fail = root
while (!q.empty()) {
int u = q.front();
q.pop();
for (const auto& kv : next_[u]) {
char c = kv.first;
int v = kv.second;
int f = fail_[u];
while (f != 0 && !next_[f].count(c)) f = fail_[f];
std::map<char, int>::const_iterator it = next_[f].find(c);
int w = it == next_[f].end() ? 0 : it->second;
fail_[v] = w;
out_[v] = ends_[w].empty() ? out_[w] : w;
q.push(v);
}
}
}
// All (pattern, start) occurrences, in the order their last character is read.
std::vector<std::pair<std::string, int> > search(const std::string& text) const {
std::vector<std::pair<std::string, int> > res;
int s = 0;
for (int i = 0; i < (int)text.size(); ++i) {
char c = text[i];
while (s != 0 && !next_[s].count(c)) s = fail_[s];
std::map<char, int>::const_iterator it = next_[s].find(c);
s = it == next_[s].end() ? 0 : it->second;
for (int k = s; k != -1; k = out_[k])
for (int idx : ends_[k])
res.push_back(std::make_pair(patterns_[idx], i - (int)patterns_[idx].size() + 1));
}
return res;
}
const std::vector<int>& fail() const { return fail_; }
private:
int newNode() {
next_.push_back(std::map<char, int>());
fail_.push_back(0);
ends_.push_back(std::vector<int>());
out_.push_back(-1);
return (int)next_.size() - 1;
}
std::vector<std::string> patterns_;
std::vector<std::map<char, int> > next_;
std::vector<int> fail_, out_;
std::vector<std::vector<int> > ends_;
};
int main() {
typedef std::vector<std::pair<std::string, int> > Matches;
AhoCorasick ac({"he", "she", "his", "hers"});
assert((ac.fail() == std::vector<int>{0, 0, 0, 0, 1, 2, 0, 3, 0, 3}));
assert((ac.search("ushers") == Matches{{"she", 1}, {"he", 2}, {"hers", 2}}));
assert(AhoCorasick({"a", "aa", "aaa"}).search("aaaa").size() == 9);
assert((AhoCorasick({"ab", "ab", "b"}).search("abab") ==
Matches{{"ab", 0}, {"ab", 0}, {"b", 1}, {"ab", 2}, {"ab", 2}, {"b", 3}}));
assert(AhoCorasick({"xyz"}).search("abc").empty());
std::cout << "aho-corasick OK\n";
return 0;
}
class AhoCorasick {
private next: Map<string, number>[] = [];
readonly fail: number[] = [];
private ends: number[][] = [];
private out: number[] = [];
constructor(private readonly patterns: string[]) {
this.newNode();
patterns.forEach((p, idx) => {
let u = 0;
for (const c of p) {
let v = this.next[u].get(c);
if (v === undefined) {
v = this.newNode();
this.next[u].set(c, v);
}
u = v;
}
this.ends[u].push(idx);
});
const q: number[] = [...this.next[0].values()]; // depth 1: fail = root
for (let head = 0; head < q.length; head++) {
const u = q[head];
for (const [c, v] of this.next[u]) {
let f = this.fail[u];
while (f !== 0 && !this.next[f].has(c)) f = this.fail[f];
const w = this.next[f].get(c) ?? 0;
this.fail[v] = w;
this.out[v] = this.ends[w].length > 0 ? w : this.out[w];
q.push(v);
}
}
}
private newNode(): number {
this.next.push(new Map());
this.fail.push(0);
this.ends.push([]);
this.out.push(-1);
return this.next.length - 1;
}
/** All [pattern, start] occurrences, in the order their last character is read. */
search(text: string): [string, number][] {
const res: [string, number][] = [];
let s = 0;
let i = 0;
for (const c of text) {
while (s !== 0 && !this.next[s].has(c)) s = this.fail[s];
s = this.next[s].get(c) ?? 0;
for (let k = s; k !== -1; k = this.out[k]) {
for (const idx of this.ends[k]) {
const p = this.patterns[idx];
res.push([p, i - p.length + 1]);
}
}
i++;
}
return res;
}
}
function check(ok: boolean, msg: string): void {
if (!ok) throw new Error(msg);
}
const same = (a: unknown, b: unknown): boolean => JSON.stringify(a) === JSON.stringify(b);
const ac = new AhoCorasick(["he", "she", "his", "hers"]);
check(same(ac.fail, [0, 0, 0, 0, 1, 2, 0, 3, 0, 3]), "fail links");
check(same(ac.search("ushers"), [["she", 1], ["he", 2], ["hers", 2]]), "ushers");
check(new AhoCorasick(["a", "aa", "aaa"]).search("aaaa").length === 9, "aaaa");
check(same(new AhoCorasick(["ab", "ab", "b"]).search("abab"),
[["ab", 0], ["ab", 0], ["b", 1], ["ab", 2], ["ab", 2], ["b", 3]]), "duplicates");
check(new AhoCorasick(["xyz"]).search("abc").length === 0, "no match");
console.log("aho-corasick OK");
Language notes. Python: dictionaries keep insertion order, so BFS order is deterministic; for big inputs the pyahocorasick C extension is 10–100× faster than pure Python. Java: Character keys box; for byte or ASCII alphabets, an int[][] table is far faster. C++: std::map<char, int> is compact and deterministic; swap in std::array<int, 26> for lowercase letters. newNode() grows next_, so the insertion loop never holds a reference into it across that call. TypeScript: for (const c of text) iterates Unicode code points, so for text with characters outside the Basic Multilingual Plane (emoji) the reported index is a code-point index, not a UTF-16 index; if you need UTF-16 offsets, iterate with text[i] instead (and accept that surrogate pairs become two "characters", which is fine as long as patterns are split the same way).
Real-world uses
- Unix
fgrep/grep -F. Aho wrote the original Unixfgreparound the Aho–Corasick algorithm: give it a file of fixed strings and it reports lines containing any of them in one pass. Modern GNU grep's fixed-string matcher (kwset) uses a Commentz–Walter / Aho–Corasick-family algorithm (Commentz–Walter, 1979, adds Boyer–Moore-style skipping to the same trie); which variant runs depends on the version and the pattern set. The Rustaho-corasickcrate, used byripgrepand the Rustregexcrate to find literal prefixes before running the full regex, implements both the failure-link (NFA) and full-DFA forms described here, plus SIMD-accelerated prefilters for small pattern sets. - Intrusion-detection signatures. Snort and Suricata check packet payloads against thousands of content strings from their rule sets. Their multi-pattern matchers ("MPM") are Aho–Corasick variants with compressed state tables (Snort's
ac,ac-bnfa,ac-splitand related options); Suricata can also use Intel's Hyperscan, a different, SIMD-heavy design. Only rules whose literal content matched are then evaluated in full. This "cheap multi-pattern filter, then expensive check" split is the typical deployment. - Antivirus scanning. ClamAV matches file contents against a very large signature database; its matcher combines an extended Boyer–Moore for plain signatures with an Aho–Corasick automaton (with a limited trie depth) for signatures containing wildcards and alternatives.
- Keyword and profanity filters. Chat moderation, comment filtering, ad-keyword targeting and "sensitive word" filters run an Aho–Corasick automaton over every message: a blocklist of thousands of words costs the same per character as a list of one. Real filters add normalization first (case folding, removing look-alike characters, collapsing repeats) because the automaton matches bytes exactly.
- DNA and protein motifs. Searching a genome for a set of short motifs (transcription-factor binding sites, restriction-enzyme sites, primer sequences, CRISPR guide targets) is a multi-pattern problem over a 4-letter alphabet, where the dense DFA is tiny and fast. The original BLAST paper (Altschul et al., 1990) describes scanning the database for the query's short "words" with a deterministic finite automaton (or a lookup table); seed-finding in similarity search is still a multi-pattern scan of this kind.
- Tokenizers and dictionaries. Dictionary-based word segmentation for languages without spaces (Chinese, Japanese) needs "every dictionary word ending at each position", which is exactly the Aho–Corasick output. Named-entity "gazetteer" taggers (find every known company, drug or place name in a document) are the same.
- Log and data scanning. Data-loss-prevention tools look for thousands of secrets, card-number prefixes or customer identifiers in outgoing data; log pipelines tag lines by keyword sets. Both are a single pass of one automaton.
- Regex engines. Engines extract the required literals of a regex (or of many regexes, as in a set of routing rules) and use a multi-literal matcher to skip text quickly; only near a literal hit does the full regex run. See Regex Mastery and the lesson on how regex engines work.
Pitfalls & edge cases
- Forgetting output links (or the chain). Reporting only
ends[state]misses patterns that are suffixes of others:heinsideshe. This is the single most common bug. - Walking the whole failure chain to report. Correct, but slow: a dictionary like
aaa…ab(never matching) on textaaaa…makes every position walk a long chain of non-terminal nodes, . Use output links, or precomputed counts if you only need counts. - Enumerating when you only need counts. can be . Count via the failure tree instead.
- Computing failure links in DFS order.
fail(v)needs the failure links of shallower nodes that may lie in other branches. DFS does not guarantee that; BFS does. - Depth-1 nodes. Their failure link must be the root. If you run the general rule from the root,
goto(root, c)is the node itself and you getfail(v) = v, an infinite loop at search time. The code above seeds the queue with depth-1 nodes to avoid this. - Duplicate patterns. Store a list of pattern ids at each terminal node (or a count). A single
patternIdfield silently drops duplicates. - Empty pattern. It matches at every position (including after the last character). Most implementations reject it; decide explicitly.
- Start index arithmetic. A match found when reading index starts at , not .
- Alphabet assumptions. A
[26]child array crashes or silently misbehaves on uppercase, digits or bytes ≥ 128. Map characters to indices explicitly, and decide on case folding before building. - Unicode. Bytes, UTF-16 code units and code points give different "characters" and different indices; patterns and text must be split the same way.
- Memory of the dense DFA. integers. For bytes and a large dictionary this is hundreds of megabytes; use maps, compressed rows, or the failure-link form.
- Mutating the dictionary. The classic automaton is static: adding a pattern can change failure links all over the trie. Rebuild, or use the online techniques in Variations.
- Recursion. Build and search are iterative; there is no recursion depth issue even for very long patterns.
Variations
- Full DFA (goto completed with failure moves). One table lookup per character, no failure loop; the right form for small alphabets, hardware/SIMD implementations, and DP/matrix-power problems over states.
- Counting via the failure tree. Add 1 at the state of each position, then sum subtrees of the failure tree (reverse BFS order): occurrences of every pattern in , independent of .
- Leftmost-longest / leftmost-first, non-overlapping matches. Search-and-replace and tokenizers want one match per region, not all overlapping ones. The Rust
aho-corasickcrate supports "standard", "leftmost-first" (priority by pattern order, like a regex alternation) and "leftmost-longest" semantics; implement by continuing until the match cannot be extended and then restarting after it. - Commentz–Walter. Builds the trie of reversed patterns and adds Boyer–Moore skip rules, so on random text with long patterns it can skip characters. Used in grep-family tools.
- Wu–Manber. A hashing-and-shift-table multi-pattern algorithm for large pattern sets (used in
agrep); fast in practice, no worst-case guarantee. - Dynamic dictionaries. "Insert/delete a pattern, query a text" online: keep automata of sizes that are powers of two and merge them like a binary counter (Codeforces 710F), or use the failure-tree Euler tour with a Fenwick tree to switch patterns on and off (Codeforces 163E).
- Wildcards. A pattern with
?wildcards can be split into its solid pieces; feed all pieces to Aho–Corasick and count, for each text position, how many pieces line up at the right offsets. - 2-D matching (Baker–Bird). Find a 2-D pattern in a 2-D text: run Aho–Corasick on the pattern's rows to label each text cell with "which pattern row ends here", then run KMP down each column on those labels.
- Relation to other structures. With one pattern, the automaton is KMP's automaton and
failis the prefix function. The failure tree of a dictionary is to Aho–Corasick what the suffix-link tree is to a suffix automaton. If the patterns change and the text is fixed, index the text with a suffix array instead.
Practice ladder
Each problem is described in my own words; follow the link for the full statement. The key solutions below use this compact builder, which returns the trie, the failure links, the node of each pattern and the BFS order (root excluded); step performs one scan step. All solutions were run against the official examples and cross-checked against brute force on random inputs.
from collections import deque
def build(patterns):
"""Trie + failure links. Returns goto (list of dicts), fail, node of each pattern, BFS order (root excluded)."""
goto, fail, node_of = [{}], [0], []
for p in patterns:
u = 0
for c in p:
if c not in goto[u]:
goto.append({})
fail.append(0)
goto[u][c] = len(goto) - 1
u = goto[u][c]
node_of.append(u)
order, q = [], deque(goto[0].values())
while q:
u = q.popleft()
order.append(u)
for c, v in goto[u].items():
f = fail[u]
while f and c not in goto[f]:
f = fail[f]
fail[v] = goto[f].get(c, 0)
q.append(v)
return goto, fail, node_of, order
def step(goto, fail, s, c):
while s and c not in goto[s]:
s = fail[s]
return goto[s].get(c, 0)
1. String Matching in an Array (LeetCode 1408) — Return the words of a small list that appear inside some other word of the list. Teaches recognizing a multi-pattern problem, even where brute force passes.
Hint
Brute force (a in b for every pair) passes the limits. For practice, build one automaton from all words and scan each word; a word counts if it is found inside a different word (beware a word matching itself).
2. Index Pairs of a String (LeetCode 1065) — Report every [start, end] where some dictionary word occurs in a text, sorted. Teaches the plain search output.
Hint
This is search() from the implementation, with end = start + len - 1, then sort the pairs. Nested matches (ab inside aba) must all appear, which is exactly what output links give you.
3. Stream of Characters (LeetCode 1032) — Letters arrive one at a time; after each, answer whether some suffix of the stream so far is a dictionary word. Teaches keeping the automaton state between queries.
Hint
Keep state between calls. Precompute hit[v]: does or anything on its failure chain end a word? Then each query is one step plus one lookup. (The popular alternative is a trie of reversed words, walked backwards over the last letters: per query instead of amortized .)
Solution
class StreamChecker:
def __init__(self, words):
self.goto, self.fail, node_of, order = build(words)
self.hit = [False] * len(self.goto)
for u in node_of:
self.hit[u] = True
for v in order: # BFS order: fail[v] is already final
self.hit[v] = self.hit[v] or self.hit[self.fail[v]]
self.s = 0
def query(self, letter):
self.s = step(self.goto, self.fail, self.s, letter)
return self.hit[self.s]
sc = StreamChecker(["cd", "f", "kl"])
assert [sc.query(c) for c in "abcdefghijkl"] == [False] * 3 + [True, False, True] + [False] * 5 + [True]
Each query is amortized (the depth bank-account argument applies across queries); building is .
4. Finding Patterns (CSES 2102) — For each of many patterns, say whether it appears in a text. Teaches marking occurrences without enumerating them.
Hint
Mark the state at every text position as "seen", then propagate "seen" from each node to its failure link in reverse BFS order. A pattern appears iff its node is seen. (Or reuse the counting solution of problem 5 and test count > 0.)
5. Counting Patterns (CSES 2103) — For each pattern, count its occurrences in a text. Teaches the failure-tree sum, which avoids the blow-up.
Hint
Do not follow output links: with patterns a, aa, … the number of matches is huge. Count visits per state, then sum each failure-tree subtree.
Solution
def count_patterns(text, patterns):
goto, fail, node_of, order = build(patterns)
hits = [0] * len(goto)
s = 0
for c in text:
s = step(goto, fail, s, c)
hits[s] += 1 # only the deepest state, not its whole chain
for v in reversed(order): # children before parents in the failure tree
hits[fail[v]] += hits[v]
return [hits[u] for u in node_of]
assert count_patterns("ushers", ["he", "she", "his", "hers"]) == [1, 1, 0, 1]
assert count_patterns("aaaa", ["a", "aa", "aaa"]) == [4, 3, 2]
Why it works: pattern occurs ending at position iff is on the failure chain of the state at (the theorem above), i.e. iff that state is in 's subtree of the failure tree. So the number of occurrences of is the number of positions whose state lies in 's subtree. Reverse BFS order visits every node after all its failure-tree descendants, because a descendant is strictly deeper. Total .
6. Pattern Positions (CSES 2104) — For each pattern, the first position (1-based) where it occurs, or −1. Teaches propagating a minimum instead of a sum.
Solution
def first_positions(text, patterns):
goto, fail, node_of, order = build(patterns)
INF = len(text)
first = [INF] * len(goto)
s = 0
for i, c in enumerate(text):
s = step(goto, fail, s, c)
first[s] = min(first[s], i) # earliest end position at this state
for v in reversed(order):
first[fail[v]] = min(first[fail[v]], first[v])
return [first[u] - len(p) + 2 if first[u] < INF else -1 for p, u in zip(patterns, node_of)] # 1-based
assert first_positions("aybabtu", ["bab", "abc", "a"]) == [3, -1, 1]
The earliest end gives the earliest start for a fixed pattern length, so propagate minimum end positions up the failure tree and convert.
7. Length of the Longest Valid Substring (LeetCode 2781) — Longest substring of a word that contains none of the forbidden strings. Teaches combining Aho–Corasick with a sliding window.
Hint
At each right end , only the shortest forbidden word ending at matters: it forces the window's left end past its start. Precompute, for each state, the length of the shortest forbidden word on its failure chain.
Solution
def longest_valid_substring(word, forbidden):
goto, fail, node_of, order = build(forbidden)
INF = float("inf")
short = [INF] * len(goto) # shortest forbidden word that is a suffix of node v
for p, u in zip(forbidden, node_of):
short[u] = min(short[u], len(p))
for v in order:
short[v] = min(short[v], short[fail[v]])
left = best = s = 0
for r, c in enumerate(word):
s = step(goto, fail, s, c)
if short[s] < INF:
left = max(left, r - short[s] + 2) # forbidden word starts at r - L + 1; skip past it
best = max(best, r - left + 1)
return best
assert longest_valid_substring("cbaaaabc", ["aaa", "cb"]) == 4
assert longest_valid_substring("leetcode", ["de", "le", "e"]) == 4
. (Because forbidden words have length at most 10 on LeetCode, checking the last 10 substrings with a hash set also passes; Aho–Corasick removes that dependence.)
8. Add Bold Tag in String (LeetCode 616) — Wrap every region of a string covered by some dictionary word in bold tags, merging overlapping and adjacent regions. Teaches turning matches into covered intervals. (Same as LeetCode 758, "Bold Words in String".)
Hint
For every match, mark cover[start..end]. With Aho–Corasick you only need the longest match ending at each position (the state's deepest terminal on its chain); a difference array or a running "covered until" pointer then marks the regions in .
9. You Are Given Some Strings... (Codeforces 1202E) — Sum, over all ordered pairs of patterns , the number of occurrences of the concatenation in a text. Teaches splitting a concatenation at the seam, and running the automaton on reversed strings.
Hint
An occurrence of is a position where some ends at and some starts at . Count patterns ending at each position (forward automaton) and patterns starting at each position (automaton of reversed patterns over the reversed text). Answer .
Solution
def pair_occurrences(t, strings):
def ends_at(text, pats):
goto, fail, node_of, order = build(pats)
cnt = [0] * len(goto)
for u in node_of:
cnt[u] += 1
for v in order: # patterns ending at v or on its chain
cnt[v] += cnt[fail[v]]
res, s = [], 0
for c in text:
s = step(goto, fail, s, c)
res.append(cnt[s])
return res
f = ends_at(t, strings) # f[x]: patterns ending at x
g = ends_at(t[::-1], [p[::-1] for p in strings])[::-1] # g[x]: patterns starting at x
return sum(f[x] * g[x + 1] for x in range(len(t) - 1))
assert pair_occurrences("aaabacaa", ["a", "aa"]) == 5
assert pair_occurrences("aaabacaa", ["a", "a", "a", "b"]) == 33
— the brute force over pairs is .
10. Genetic engineering (Codeforces 86C) — Count DNA strings of length in which every position is covered by at least one occurrence of a given set of short motifs. Teaches DP over automaton states.
Hint
State = (automaton node, how many trailing characters are still uncovered). Use the full DFA over ACGT. When appending a letter, the longest motif ending here (deepest terminal on the chain) covers the last len characters; if it is at least the uncovered count, everything becomes covered. The uncovered count is bounded by the longest motif. Count with DP over length; see String DP.
11. Legen... (Codeforces 696D) — Each pickup line has a happiness value; maximize the total happiness of all occurrences in a text of length up to . Teaches automaton + (max, +) matrix exponentiation.
Hint
Each DFA state has a gain = sum of values of patterns on its chain. "Best total over exactly steps" is a max-plus matrix power of the transition matrix (at most about 200 states). See Matrix Exponentiation.
12. e-Government (Codeforces 163E) — A fixed set of surnames, each switchable on and off; queries ask for the total number of occurrences of active surnames in a given text. Teaches the failure tree with an Euler tour and a Fenwick tree.
Hint
Occurrences of pattern at a position = [state lies in 's failure-tree subtree]. Flip it around: for a state , the number of active patterns ending there = number of active patterns that are ancestors of in the failure tree. Activating adds +1 to its whole subtree (a range in Euler-tour order); a query sums point values at the states visited by the text. Range update + point query on a Fenwick tree.
13. String Set Queries (Codeforces 710F) — Online insertions and deletions of patterns, interleaved with "count occurrences of all current patterns in this text" queries. Teaches making a static structure dynamic.
Hint
Keep separate automata whose sizes are distinct powers of two (like binary counter digits); inserting merges equal-sized ones and rebuilds. Each pattern is rebuilt times. Deletions: a second family of automata for deleted patterns, subtract the counts.
Common mistakes & interview follow-ups
"Why not just run KMP for each pattern?" That reads the text times, . Aho–Corasick reads it once, . With one pattern they coincide: the automaton is KMP's.
"Why BFS for failure links?" fail(v) is computed from failure links of strictly shallower nodes, possibly in other branches. BFS finishes all shallower nodes first; DFS does not.
"Prove the search is linear." Depth argument: each character raises the state's depth by at most one; each failure move lowers it by at least one; depth is never negative. So at most failure moves in total. Reporting is one output link per match.
"What if you need counts, not positions?" Count per state, sum over failure-tree subtrees, ; do not enumerate matches.
"What is the memory for a byte alphabet with 10,000 signatures?" Up to states. A full table is entries each; mention compressed rows, maps, or keeping the failure-link form. Real IDS engines spend most of their design effort here.
"How would you support adding patterns at runtime?" Rebuild periodically, or the binary-grouping trick (logarithmic number of automata). Mention that most production systems rebuild on rule updates and swap atomically.
"Non-overlapping replacement (censor words)?" Use leftmost-longest semantics: when a match ends, prefer the longest; replace; restart at the root just after the match. Watch for overlapping banned words like ass in class — normalization and word boundaries matter more than the algorithm.
"How is this different from a suffix automaton or suffix array?" Those index the text (any pattern queried later); Aho–Corasick indexes the patterns (any text scanned later).
Mistakes interviewers watch for: reporting only the current node (missing he in she); fail(v) = v for depth-1 nodes; computing failure links in DFS order; walking the whole failure chain for every character to collect outputs; storing one pattern id per node (losing duplicates); wrong start index ( instead of ).
Quick quiz
1. For the patterns he, she, his, hers, what is fail(she) and why does she need an output link?
Answer
fail(she) = he: the proper suffixes of she are he, e and empty, and he is the longest one in the trie. he is itself a pattern, so out(she) = he: whenever the scanner reaches she, the pattern he has also just ended.
2. The dictionary is a, ab, bab, bc, bca, c, caa and the text is abccab. List all matches as (pattern, start).
Answer
a@0, ab@0, bc@1, c@2, c@3, a@4, ab@4 — seven matches (checked by running the implementation). bca never completes: after abc the next letter is c, not a.
3. Patterns a, aa, aaa, aaaa; text . How many matches does a full enumeration report, and how would you count per pattern without enumerating?
Answer
. Count visits per state (the state after position is always aaaa), then add each node's count to its failure link in reverse BFS order; the counts come out as 10, 9, 8, 7.
4. A single text character causes five failure moves. Does that break the bound for the scan?
Answer
No. The bound is amortized: those five moves each lowered the state's depth, and the depth had to be built up by at least five earlier characters that each moved down by one. Over the whole text, failure moves ≤ characters.
5. You build the full DFA for 50,000 patterns of average length 16 over bytes. Estimate the table size with 4-byte state ids.
Answer
Up to states, times 256 entries, times 4 bytes ≈ 820 MB. Shared prefixes reduce the state count, but this is why real matchers compress rows or keep the failure-link form.
Further reading / sources
- Alfred V. Aho and Margaret J. Corasick, "Efficient string matching: an aid to bibliographic search", Communications of the ACM 18(6):333–340, 1975 — the original paper (goto, failure and output functions; the linear-time bounds).
- Dan Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997, §3.4 "Exact matching with a set of patterns" (Aho–Corasick, failure-link correctness, and applications to DNA).
- Maxime Crochemore, Christophe Hancart, Thierry Lecroq, Algorithms on Strings, Cambridge University Press, 2007, ch. 2 (dictionary automata).
- Beate Commentz-Walter, "A string matching algorithm fast on the average", ICALP 1979.
- Sun Wu and Udi Manber, "A fast algorithm for multi-pattern searching", Technical Report TR-94-17, University of Arizona, 1994.
- Stephen F. Altschul, Warren Gish, Webb Miller, Eugene W. Myers, David J. Lipman, "Basic local alignment search tool", Journal of Molecular Biology 215(3), 1990.
- cp-algorithms: Aho-Corasick algorithm — the automaton (DFA) form and competitive-programming applications.
- Andrew Gallant, the Rust
aho-corasickcrate documentation — match semantics (standard, leftmost-first, leftmost-longest), NFA vs DFA forms, and prefilters. - Snort 2 user manual, "config detection: search-method" (the
ac,ac-bnfa,ac-splitmulti-pattern matchers); ClamAV documentation on its signature matchers (Boyer–Moore and Aho–Corasick).
Previous lesson: The Z-Algorithm · Next lesson: Suffix Arrays & LCP
Related: String Algorithms overview · KMP & the Prefix Function · Tries · BFS in Depth · String Hashing in Depth · Suffix Automaton · Course home