Knuth-Morris-Pratt finds one pattern in one text in
O(n+m) time — but its own Pitfalls section admits a real limit: search for
k different patterns in the same text by running KMP k separate times, and
the text gets rescanned from scratch every time, O(k·(n+m)) total. Aho-
Corasick fixes that by building every pattern into a single
trie first, then generalizing KMP's failure-link trick from
"the pattern compared against itself" to "every trie node compared against every other node" — one
failure link per trie node instead of one per pattern position — so the whole text is scanned
exactly once, however many patterns are loaded into the trie. The demo below builds a trie of four
words (he, she, his, hers) that share several
prefixes, computes nine failure links across it, then scans the text "ushers" once and
correctly reports three overlapping matches — including one, "he" at index 2, that only
shows up because a failure link points from one already-matched pattern straight to another.
The trie holds four fixed patterns — he, she, his, hers — chosen because they
overlap in exactly the way that makes "many patterns, one automaton" concrete: he is
itself a stored pattern and a prefix of hers, the same double-duty a node can
have in any trie (see trie's Pitfalls). Step
through two phases: first, a failure link is computed for every node, shallowest
first — the exact same "longest prefix that's also a suffix" idea as KMP's LPS table, just applied
to whichever pattern-prefix a trie node represents instead of one pattern compared against itself;
watch the dashed lines appear on the trie one at a time. Then the automaton scans
"ushers" once, left to right: a solid trie edge (a "goto") when the next character keeps it
on a known path, a dashed failure-link jump when it doesn't — never a wasted look at a text
character. Watch index 3: the walk lands on the node for she and reports it —
and, in the same step, follows that node's own failure link up to the node for
he and reports it too, because he is a suffix of the just-matched
she and happens to be a stored pattern in its own right.
Every trie node represents one specific string — the characters on the path from the root down to
it. KMP's failure link for pattern position i answers "if the match breaks right after
this point, what's the longest prefix of the pattern that's also a suffix of what's already matched,
so comparing can resume there instead of from scratch?" Aho-Corasick asks the identical question for
every trie node's own path-string: fail(v) is the trie node representing the longest
proper suffix of v's path that is also some prefix stored in the trie — the
longest suffix that is itself a real, walkable path from the root. Computing it needs every shallower
node's failure link already finalized (the same "build in order, reuse what's known" constraint the
LPS table has), so the build walks the trie shallowest-first: a node's failure link is either the
root (for anything one character deep) or found by walking its parent's failure chain
looking for a child with the same character — one comparison-and-possible-fallback, the same shape as
KMP's own build step, just resolved through a different node's already-known failure link instead of
the same pattern compared against itself.
The one genuinely new idea, since KMP only ever tracks one pattern: a node's failure link
can point at a different pattern's own ending. In the demo, fail(she) = he —
the trie node for she fails not to the root but directly to the node that marks the end
of he. So finding she at some position means he is
guaranteed to also end there, without rescanning a single character: reporting a match at
any node means walking its entire failure chain back to the root and reporting every
pattern-end found along the way, not just checking the current node itself (see Pitfalls for what
happens when that chain-walk gets skipped).
Matches the demo above — trie build, then failure-link BFS, then a single scanning pass:
class Node {
children = new Map();
isEnd = false;
patterns = []; // pattern(s) ending exactly here
fail = null;
}
function buildTrie(patterns) {
const root = new Node();
for (const pat of patterns) {
let node = root;
for (const ch of pat) {
if (!node.children.has(ch)) node.children.set(ch, new Node());
node = node.children.get(ch);
}
node.isEnd = true;
node.patterns.push(pat);
}
return root;
}
function computeFailLinks(root) {
const queue = [];
for (const child of root.children.values()) {
child.fail = root; // depth 1: nothing shorter to fall back to
queue.push(child);
}
for (let qi = 0; qi < queue.length; qi++) {
const u = queue[qi];
for (const [c, v] of u.children) {
let f = u.fail;
while (f !== root && !f.children.has(c)) f = f.fail;
const cand = f.children.get(c);
v.fail = (cand && cand !== v) ? cand : root;
queue.push(v);
}
}
}
function search(root, text) {
const matches = [];
let node = root;
for (let i = 0; i < text.length; i++) {
const c = text[i];
while (node !== root && !node.children.has(c)) node = node.fail;
if (node.children.has(c)) node = node.children.get(c);
for (let t = node; t !== root; t = t.fail) {
for (const p of t.patterns) matches.push({ pattern: p, start: i - p.length + 1, end: i + 1 });
}
}
return matches;
}
The BFS in computeFailLinks has to process nodes in non-decreasing depth order — a
node's own failure link depends on its parent's, and root's children start as trivial base cases.
search's inner loop is the output-chain walk from the Why-it-works section: it runs
every time the automaton advances, not only when node.isEnd is true, because a match
further down the failure chain is just as real as one sitting on the current node.
Skipping the failure-chain walk on a match silently drops matches. It's tempting
to check only node.isEnd after each step, the way a single-pattern search would — but a
node's failure chain can pass through other pattern-ends that are just as real. On the
shipped example, an isEnd-only variant of the search above finds she and
hers but silently drops he entirely: the automaton is sitting on the
she node when the match happens, and she's own isEnd flag says
nothing about the he pattern-end sitting one hop up its failure chain. Checked, not just
asserted — an isEnd-only variant of the exact reference implementation above, run against the shipped
patterns and text, returns [she@1, hers@2] instead of the correct
[she@1, he@2, hers@2].
The whole point is not rescanning the text once per pattern. Running KMP once for
each of the four shipped patterns against "ushers" takes 25 comparisons
total across four separate passes — instrumented directly, not an even 4 × 6 = 24:
he, she, and hers each take exactly 6 (one per character), but
his takes 7, one extra backtrack against this particular text. The automaton above scans
the text once, needing only 7 transition attempts total (six characters, plus one
extra failure-link hop when the walk falls off the she node looking for r).
That gap only widens with more patterns — Aho-Corasick's reason to exist is that its scan cost is
O(n) regardless of k, where naively repeating KMP costs O(k·n).
Building the automaton has its own upfront cost — but it's paid back sooner than "many
texts" suggests. Constructing the trie and computing every failure link costs
O(m), where m is the combined length of all patterns, before a single text
character gets scanned. See measuring the break-even below:
against a single pattern this cost is never earned back, no matter how many texts get scanned, because
the automaton then degenerates into exactly the structure KMP already builds on its own. But the
moment there are two or more patterns, the build cost is paid back within a fraction of the very first
text scanned, not after accumulating many of them — a spam filter's keyword list or an
intrusion-detection signature set doesn't need a long stream of texts to justify building the
automaton, just more than one pattern and a text that isn't tiny.
The Pitfalls section above names two separate conditions for when the automaton's build cost pays
off — "many patterns, or the same pattern set searched against many texts" — without saying how many
of either. Measured here: this page's own shipped buildTrie/computeFailLinks/
search against kmp.html's own shipped
computeLPS/kmpSearch, run once per pattern. Correctness cross-checked first:
5,000 random trials over small alphabets (2-6 symbols, chosen specifically to force overlapping
prefixes and failure-link hops rather than easy all-distinct-character matches), comparing the
automaton's full match set against the naive per-pattern result — 0 mismatches.
Against a single pattern, the build cost is never earned back, at any number of texts.
With k=1 the trie is a single chain and its failure links are exactly KMP's own LPS
table, so the two scan passes are byte-for-byte identical: an 8-character pattern
("whatever") scanned against random text of every length tested, 50 to 5,000 characters,
produces the exact same operation count both ways. The only difference is the one-time build —
16 operations for the automaton against 7 for plain KMP's LPS table —
and there's nothing on the other side of the ledger to pay that back, however many texts get scanned.
This sharpens the Pitfalls claim above: it isn't just overhead "for a one-off search," it's permanent
overhead for exactly one pattern, full stop.
With two or more patterns, the break-even isn't "many texts" — it's a fraction of the first one. Solving (automaton build cost − naive build cost) ÷ (naive per-text cost − automaton per-text cost) for how many texts it takes to pay the build cost back, averaged over 5 random pattern sets per cell (patterns 4-8 characters, text drawn from a 26-letter alphabet):
patterns (k) text length (n) texts to break even
2 100 0.1640
2 10,000 0.0016
5 100 0.0971
5 10,000 0.0010
10 100 0.0863
10 10,000 0.0009
50 100 0.1001
50 10,000 0.0010
Every cell is well under a single text — the automaton's one-time build cost gets paid back within
the first text scanned, not after accumulating a stream of them, the moment the set holds more than
one pattern. The break-even count barely moves with k past 2 (tightening from 0.16 to
0.10 texts at n=100 across a 25× range in pattern count) because both the automaton's build cost
and the naive approach's per-text cost scale with k in roughly the same proportion; what
actually drives the ratio down is text length, since a fixed one-time build cost matters less the
longer each text is. "Build once, scan many" is true, but the real threshold for "many" is the
pattern count crossing one, not the text count crossing some larger number — a
single long text already justifies the automaton, as long as it's matched against more than one
pattern.
Time: O(m) to build the trie and compute every failure link, where
m is the total length of all patterns combined (12 characters across the four shipped
patterns, collapsed onto 9 edges since he and his share a prefix) — the BFS
visits each node once, and the inner while loop's total work across the whole build is
bounded the same way KMP's own build is bounded, by how far the fallback pointer can retreat before
it needs to advance again. Then O(n + z) to scan, where n is the text
length and z is the number of matches actually reported — the automaton's position in
the trie only gets shallower on a failure-link hop and only gets deeper on a goto, so (the same
accounting argument KMP's Complexity section makes) the total number of hops across the whole scan is
bounded by the total number of times it was able to get deeper, which is itself bounded by
n. See measuring the break-even above for how quickly
that one-time O(m) build cost is actually recovered against a real alternative.
Space: O(m) for the trie and its failure links, O(1) beyond
that during the scan (excluding the matches themselves) — the text is scanned once, left to right,
never copied or re-read.
Aho-Corasick indexes a known set of patterns against a text scanned once. Suffix Array inverts that relationship: it indexes the text once, so that patterns nobody knew about at indexing time can still be searched cheaply later, with a pair of binary searches per query instead of a fresh scan. See Choosing an Exact-Match String Matcher for how multi-pattern search compares to the other fifteen exact-match entries.