Aho-Corasick — multiple pattern search, automaton: Visual walkthrough

Step 1 — Draw the words as a tree (the trie)

WHAT. We stack all four words into a single tree where every edge carries one letter and every node is a "word-so-far" — a prefix.

WHY. If we kept each word separate we'd re-scan shared beginnings again and again. he, her, hers all start with he; a tree lets that shared start be walked once. This shared-prefix tree is exactly a trie.

PICTURE. Follow the black edges from the top circle (the root — the empty word). Reading letters down to a node spells that node's string. The red rings are terminal nodes: a full dictionary word ends there.

Figure — Aho-Corasick — multiple pattern search, automaton

Nothing here needs failure links yet. Step 1 is pure spelling.

Step 2 — The problem a plain trie can't solve

WHAT. Try to match the text with the trie alone and watch it break.

WHY. We must see the pain before we build the cure. Start at root, read u, s, h, e — we reach node she. Now the next text letter is r. Node she has no edge on r. A naive trie says "dead end, go back to root" — and we throw away everything.

PICTURE. The red X marks the missing edge. If we restart at root on r, we lose the fact that we just matched he (the tail of she), so we'd miss hers a moment later.

Step 3 — Define the shortcut rope precisely

WHAT. For every node $v$ we define one arrow, its failure link $fail [v]$ .

WHY. We need a rule, not a guess, so a computer can build it. The rule: land on the node whose string is the longest proper suffix of $str (v)$ that is still a node in the trie.

Let's unpack every word of that:

suffix of she: any tail — he, e, "".
proper suffix: a tail that is not the whole string — so she itself is excluded.
"that is still a node": it must be spellable in our trie (a prefix of some pattern).

Among she's proper suffixes, he is a node, e is not, "" (root) always is. The longest node is he. So $fail [she] = he$ .

PICTURE. The single red arrow is the failure link she → he. Notice it always points to a strictly shorter string (fewer letters), and never downward.

Step 4 — Why we must build these ropes shortest-first (BFS)

WHAT. We compute all failure links by walking the trie in breadth-first order — depth 1 nodes, then depth 2, then depth 3…

WHY. A failure link always points to a shorter string (Step 3). So when we process node $v$ , every node its rope could touch has fewer letters, i.e. smaller depth, and is therefore already done. Process shallow before deep and nothing is ever "not ready".

PICTURE. The trie coloured by depth-layer. The red layer is the frontier BFS is currently filling; every arrow leaving it points up into an already-finished (black) layer.

Step 5 — The parent-chain rule that computes each rope

WHAT. Turn "longest proper suffix that's a node" into a mechanical computation using the parent's rope.

WHY. We don't want to test every suffix by hand. Here's the shortcut. Let $v$ 's parent be $p$ , reached by letter $c$ , so $str (v) = str (p) + c$ . Any proper suffix of $str (v)$ ending in $c$ looks like $s + c$ where $s$ is a proper suffix of $str (p)$ . The proper suffixes of $p$ that are nodes are exactly $fail [p], fail [fail [p]], \dots$ — the failure chain of the parent. So:

Walk up $p$ 's failure chain. At the first node $u$ that owns a child on $c$ , jump onto that child. That child is $fail [v]$ .

PICTURE. For $v = she$ : parent $p = sh$ , letter $c = e$ . Follow the red chain from sh: $fail [sh] = h$ . Does h have a child on e? Yes → he. So $fail [she] = he$ , matching Step 3.

Step 6 — Fill in every transition (no dead ends left)

WHAT. Replace "on a mismatch, chase the failure chain" with a complete table $δ (v, c)$ that has an answer for every node and every letter.

WHY. At query time we want one lookup per character — no chain-walking. So we precompute where each (node, letter) really goes. The definition just says: if there's a real edge, take it; otherwise take the failure link's answer for the same letter (which BFS already computed).

PICTURE. Node she, letter r: no real edge (the X from Step 2). We copy the answer of $δ (fail [she], r) = δ (he, r) = her$ . The red dashed arrow is the filled-in transition she --r--> her. The dead end is gone.

This is now a genuine DFA: total, deterministic, one move per letter.

Step 7 — Every landing may shout several words (output links)

WHAT. When we land on a node, we report not only that node's word but every pattern that ends as a suffix here — found by following failure links up to root.

WHY. Land on she. Its string is "s-h-e"; the tail "h-e" is also a full pattern he, ending at the very same text position. That match hides on the failure chain, not on the current node. Following fail from she reaches he (terminal) → report both.

PICTURE. The red chain of dictionary links from she: she(✓) → he(✓) → root. Two red rings on the path = two matches at this position.

Step 8 — Run the whole text through the finished machine

WHAT. Slide one finger through ushers, taking exactly one $δ$ -step per letter and shouting matches from each landing.

WHY. This is the payoff: after all the building, scanning is a flat loop, $O (n + z)$ — independent of how many patterns we stored, just like KMP is for one pattern (KMP — single pattern matching).

PICTURE. The path traced through the automaton. Each dot is a landing; the two red dots (at e and the final s) are where words are shouted.

char	$δ$ move	landing	shouts	why
u	$δ (root, u)$	root	–	no `u` edge, stay at root
s	root→s	s	–	real edge
h	s→sh	sh	–	real edge
e	sh→she	she	she, he	terminal + output chain to `he`
r	$δ (she, r)$ = her	her	–	filled transition (Step 6)
s	her→hers	hers	hers	real edge, terminal

The transition at r is the moment Step 2's dead end would have cost us hers. The failure link paid off.

The one-picture summary

Everything above, compressed: Trie (black tree) → Tie (red failure links) → Try (the text path). One machine, one pass.

Recall Feynman: the whole walkthrough in plain words

I wrote my forbidden words he, she, his, hers into one letter-tree so shared starts share branches (Step 1). Then I tried to read ushers and got stuck spelling she because there was no r branch (Step 2) — and quitting to the top would have lost hers. So on every node I drew a rescue rope to the node spelling its longest tail-that-is-still-a-word-start; she's rope goes to he (Step 3). I drew these ropes shortest-word-first, because a rope always leads to a shorter word that's already finished (Step 4), and I found each rope by hopping up the parent's ropes until a matching branch appeared (Step 5). To make reading instant I pre-filled a move for every node-and-letter: real branch if it exists, else copy the rope's move (Step 6). Since a short word can hide as the tail of a longer one, at every landing I follow ropes upward and shout every finished word on the way (Step 7). Finally I slid one finger through ushers, one move per letter, shouting she+he at the e and hers at the last s (Step 8). Build once, scan once — done.

Flashcards

In the trie for {he, she, his, hers}, what string does node she represent?

The prefix "s-h-e".

Why does a plain trie fail on text ushers at the r after reaching she?

she has no r edge; restarting at root would discard the matched suffix he and miss hers.

What is fail[she] and how do we get it from the parent chain?

he; from parent sh, follow fail[sh]=h, and h has a child on e → he.

Why compute failure links in BFS (increasing depth) order?

A failure link points to a strictly shorter string, so it is already finished when we reach the deeper node.

What is δ(she, r) after the transition table is filled?

her — copied from δ(fail[she], r) = δ(he, r).

At the landing she, which words are shouted and why?

she and he; he is a suffix ending at the same position, found via the dictionary-link chain.