Worked examples — Aho-Corasick — multiple pattern search, automaton

---

The scenario matrix

Before working examples, let us list every distinct case-class the automaton can hit. Each later example is tagged with the cell it covers so you can see nothing is skipped.

#	Case class	What is unusual	Covered by
C1	Degenerate: empty text	text length $n=0$, machine never leaves root	Ex 1
C2	Degenerate: single-char patterns	pattern length 1, terminal sits at depth 1	Ex 1
C3	Miss at root	text char has no edge from root; $\delta (\text{root},c)=\text{root}$	Ex 2
C4	Nested patterns (one is a prefix of another)	e.g. he inside hers — both report at their own ends	Ex 3
C5	Suffix-sharing patterns (dictionary chain)	she ends and he also ends at the SAME position	Ex 3
C6	Deep failure jump	mismatch forces a fall-back several levels up	Ex 4
C7	Multiple matches from one state	one landing triggers 2+ reports via dictionary link	Ex 5
C8	Overlapping occurrences of the SAME pattern	pattern found again starting inside its previous copy	Ex 6
C9	Real-world word problem	build a profanity/keyword filter, count hits	Ex 7
C10	Exam twist: fail vs goto confusion	proves fail is a node equal to a suffix, not a child	Ex 8

Every quadrant of "what can go weird" (empty / tiny / miss / nested / shared / deep / multiple / overlapping / applied / trap) is one row above.

---

Example 1 — Degenerate inputs (C1, C2)

Forecast: guess — how many matches for the empty text? And for ab, where do the reports land?

Steps.

1. Build the trie. Root has two children: node a (terminal for a) and node b (terminal for b). Why this step? We must always have the structure before scanning; single-char patterns just make terminals sit at depth 1.
2. Failure links. Root's children get $\text{fail}=\text{root}$ by the base rule. Why this step? Depth-1 nodes have no proper suffix longer than the empty string, so they fall back to root.
3. Scan "". The loop over characters never runs. State stays at root; root is not terminal. Why this step? An empty text feeds zero characters, so the machine cannot move — 0 matches is forced by the definition.
4. Scan ab.
   • char a: $\delta (\text{root},a)=$ node a → report a (position 0).
   • char b: $\delta (\text{a},b)$: node a has no child b; follow $\text{fail}[a]=\text{root}$; root has child b → node b → report b (position 1).

Verify: Total matches on ab $=2$ (a at index 0, b at index 1); on "" $=0$. Each length-1 pattern matched exactly once — consistent with ab containing one a and one b.

---

Example 2 — Miss at the root (C3)

Forecast: the leading x matches nothing — does the machine reset cleanly, or get confused?

Steps.

1. Trie: root → c → ca → cat(✓cat).
2. char x: root has no child x. Rule: $\delta (\text{root},x)=\text{root}$. Why this step? Root is its own failure sink; a char with no edge from root simply keeps us at root — no progress lost because there was none.
3. char c: $\delta (\text{root},c)=$ node c. Why this step? Real edge exists, so we take it.
4. char a: c→ca. char t: ca→cat → report cat (ends at index 3).

Verify: cat occurs in xcat once, ending at index 3 (0-based). The junk prefix x cost us nothing — exactly one match reported. ✓

---

Example 3 — Nested + suffix-sharing patterns (C4, C5)

Forecast: at which single character do two words fire at once?

Steps.

1. Trie strings: h, he(✓), her, hers(✓), s, sh, she(✓), hi, his(✓). Why this step? We need the tree so failure links have somewhere to point.
2. Key failure link: longest proper suffix of she that is a trie node is he, so $\text{fail}[\text{she}]=\text{he}$. Why this step? This rope is what lets one landing report two words: he is terminal and sits on she's dictionary chain.
3. Scan u s h e r s (see figure — follow the coloured path):

   char	state	reports
   u	root	–
   s	s	–
   h	sh	–
   e	she	she, he
   r	her	–
   s	hers	hers
   Why the double report at e? Landing on she (terminal) we walk its dictionary link to he (also terminal) → both fire. That is cell C5.

4. Why r did not restart at root (C6 preview): node she has no child r; $\delta (\text{she},r)$ follows $\text{fail}[\text{she}]=\text{he}$, and he does have a child r → her. Progress preserved.

Verify: matches on ushers = she (index 1–3), he (index 2–3), hers (index 2–5): total 3 matches. Nesting: he reported inside hers's region, she/he share the endpoint at index 3. ✓

---

Example 4 — Deep failure jump (C6)

Forecast: after spelling abcd, if the next char were x, how many levels do we drop?

Steps.

1. Trie: one long branch a→ab→abc→abcd(✓), plus branches b→bc→bcd(✓), c→cd(✓), d(✓).
2. Failure links (each points to the same suffix one letter shorter): $\text{fail}[abcd]=bcd$, $\text{fail}[bcd]=cd$, $\text{fail}[cd]=d$, $\text{fail}[d]=\text{root}$. Why this step? Because bcd is the longest proper suffix of abcd that is a node, and so on down.
3. Scan abcd: we walk straight down the long branch. At the final node abcd we report abcd, then follow the dictionary chain abcd → bcd → cd → d — all four patterns end here! Why this step? Every shorter pattern is a suffix ending at the same index, so all live on one dictionary chain.
4. The deep jump. Suppose one more char x arrives. $\delta (abcd,x)$: no edge; try $\text{fail}[abcd]=bcd$ (no x), then cd (no x), then d (no x), then root (no x) → land at root. We climbed 4 levels in one query step — but this cost is amortised into build time.

Verify: matches on abcd = {abcd, bcd, cd, d}, total 4, all ending at index 3. ✓

---

Example 5 — Multiple matches from one state via dictionary chain (C7)

Forecast: which single character produces two reports at once?

Steps.

1. Trie: a(✓)→ab(✓), b→bc(✓), c(✓).
2. Failure links: $\text{fail}[ab]=b$ (longest proper suffix of ab that is a node is b), $\text{fail}[bc]=c$ (suffix c is a node & terminal). Why this step? $\text{fail}[bc]=c$ is exactly the rope that will chain two matches.
3. Scan a b c:
   • a: node a → report a.
   • b: node ab → report ab.
   • c: $\delta (ab,c)$: ab has no c; $\text{fail}[ab]=b$; b has child c → node bc → report bc, then dictionary link $\text{fail}[bc]=c$ (terminal) → report c. Why this step? One state (bc) triggers two reports (bc, c) — that is cell C7. Never stop at the terminal flag; always walk the chain.

Verify: matches on abc = a(idx0), ab(idx0–1), bc(idx1–2), c(idx2): total 4. The c at index 2 was found only by following the output link from bc. ✓

---

Example 6 — Overlapping occurrences of the same pattern (C8)

Forecast: four as — is the answer 2 (non-overlapping) or 3 (overlapping)?

Steps.

1. Trie: root → a → aa(✓aa). Failure links: $\text{fail}[a]=\text{root}$, $\text{fail}[aa]=a$. Why this step? Longest proper suffix of aa is a, which is a node — this rope keeps one a of progress after each match.
2. Scan a a a a:
   • idx0 a: node a, no report.
   • idx1 a: a→aa → report aa (ends idx1).
   • idx2 a: $\delta (aa,a)$: aa has no child a; $\text{fail}[aa]=a$; a→aa → report aa (ends idx2).
   • idx3 a: same fall-back → aa (ends idx3). Why this step? The failure link $\text{fail}[aa]=a$ means after matching we still "remember" one trailing a, so the next a completes an overlapping copy. Aho-Corasick reports overlapping matches automatically.

Verify: occurrences of aa in aaaa (overlapping) = at ending indices {1, 2, 3} → 3 matches. ✓

---

Example 7 — Real-world word problem (C9)

Forecast: does badman count as its own hit and still let bad/mad inside it count?

Steps.

1. Trie: b→ba→bad(✓bad)→badm→badma→badman(✓badman), and m→ma→mad(✓mad).
2. Failure links that matter:
   • $\text{fail}[badm]=m$ (suffix m is a node).
   • $\text{fail}[badman]=$ longest proper suffix of badman that is a node; man is not a pattern-prefix, an,n are not nodes → $\text{fail}[badman]=\text{root}$. Why this step? We must know where badm... falls back so mad inside badm can be caught.
3. Scan b a d m a d b a d m a n (indices 0..11):
   • idx2 d: node bad → bad.
   • idx3 m: node badm (real edge, bad→m exists).
   • idx4 a: badm→badma.
   • idx5 d: badma→ no child d? Path badma has child n only. $\delta (badma,d)$: $\text{fail}[badma]=ma$ (suffix ma is a node), ma has child d → node mad → mad. Why this step? The rope from the badm... branch lands us in the mad branch — catching an embedded word.
   • idx6 b…idx8 d: rebuild bad → bad (second one).
   • idx9 m→idx11 n: continue badm badma badman → at idx11 node badman → badman.
4. Total reports. bad (idx0–2), mad (idx3–5), bad (idx6–8), badman (idx6–11). Why this step? badman reports as itself; the bad prefix inside it already reported at idx8 — nested matches all count.

Verify: hits = 2×bad + 1×mad + 1×badman = 4 total flagged occurrences. ✓

---

Example 8 — Exam twist: fail is a node, not a child (C10)

Forecast: does the failure link ever point below its target string's length?

Steps.

1. Definition recall. $\text{fail}[v]$ is the node whose string equals the longest proper suffix of $\text{str}(v)$. It is never a child of that node — a child would be longer, contradicting "suffix." Why this step? This is the exact trap in the parent's mistake list ("failure links go to a child of the suffix node"). We test it.
2. Compute. $\text{str}(ab)=$ ab. Its proper suffixes are b and `` (empty). The longest that is a trie node is b. So $\text{fail}[ab]=$ node b itself. Why this step? Matching the definition directly, not the intuition-trap.
3. Verdict. The claim is FALSE. $\text{fail}[ab]=$ node b, which has depth 1 (shorter than ab's depth 2). A failure link always points upward or sideways to strictly shorter depth, never to a deeper child.

Verify: depth of $\text{fail}[ab]$ = 1 < depth of ab = 2, and $\text{str}(\text{fail}[ab])=$b is a proper suffix of ab. Both conditions of the definition hold; the "child" claim violates the depth inequality. ✓

---

Recall Which cells did we cover?

C1 empty text ::: Ex 1 C2 single-char patterns ::: Ex 1 C3 miss at root ::: Ex 2 C4 nested patterns ::: Ex 3 C5 suffix-sharing dictionary chain ::: Ex 3 C6 deep failure jump ::: Ex 4 C7 multiple matches from one state ::: Ex 5 C8 overlapping same-pattern ::: Ex 6 C9 real-world filter ::: Ex 7 C10 fail-vs-goto exam trap ::: Ex 8

---

See also

• KMP — single pattern matching — the failure function this generalises.
• Trie — prefix tree — the skeleton we drove through.
• BFS — breadth-first search — the order that made failure links computable.
• Finite Automata — DFA/NFA — what the completed $\delta$ table is.
• Z-algorithm and string matching, Suffix Automaton, Suffix Tree — cousins for other string tasks.