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

3.8.6 · D3 · Coding › String Algorithms › Aho-Corasick — multiple pattern search, automaton

---

The scenario matrix

Examples pe kaam karne se pehle, chaliye har distinct case-class list karte hain jo automaton hit kar sakta hai. Baad ke har example ko us cell ke saath tag kiya gaya hai jise woh cover karta hai, taaki dekh sako ki kuch skip nahi hua.

#	Case class	Kya unusual hai	Covered by
C1	Degenerate: empty text	text length $n=0$, machine kabhi root nahi chhodti	Ex 1
C2	Degenerate: single-char patterns	pattern length 1, terminal depth 1 pe baithta hai	Ex 1
C3	Miss at root	text char ka root se koi edge nahi; $\delta (\text{root},c)=\text{root}$	Ex 2
C4	Nested patterns (ek doosre ka prefix hai)	jaise he andar hers — dono apne ends pe report karte hain	Ex 3
C5	Suffix-sharing patterns (dictionary chain)	she ends aur he bhi SAME position pe ends karta hai	Ex 3
C6	Deep failure jump	mismatch kai levels upar fall-back karne pe majboor karta hai	Ex 4
C7	Multiple matches from one state	ek landing 2+ reports trigger karta hai dictionary link ke zariye	Ex 5
C8	Overlapping occurrences of the SAME pattern	pattern phir milta hai apni pichli copy ke andar se start hokar	Ex 6
C9	Real-world word problem	ek profanity/keyword filter banao, hits count karo	Ex 7
C10	Exam twist: fail vs goto confusion	prove karta hai ki fail ek node equal to a suffix hai, child nahi	Ex 8

"Kya galat ho sakta hai" ke har quadrant (empty / tiny / miss / nested / shared / deep / multiple / overlapping / applied / trap) ka ek row upar hai.

---

Example 1 — Degenerate inputs (C1, C2)

Forecast: guess karo — empty text ke liye kitne matches? Aur ab ke liye, reports kahan land honge?

Steps.

1. Trie banao. Root ke do children hain: node a (a ke liye terminal) aur node b (b ke liye terminal). Yeh step kyun? Scanning se pehle hamesha structure hona chahiye; single-char patterns sirf terminals ko depth 1 pe bithate hain.
2. Failure links. Root ke children ko base rule se $\text{fail}=\text{root}$ milta hai. Yeh step kyun? Depth-1 nodes ka koi proper suffix empty string se lamba nahi hota, toh woh root pe fall back karte hain.
3. "" scan karo. Characters ke upar loop kabhi run nahi karta. State root pe rehti hai; root terminal nahi hai. Yeh step kyun? Empty text zero characters feed karta hai, toh machine move nahi kar sakti — 0 matches definition se forced hai.
4. ab scan karo.
   • char a: $\delta (\text{root},a)=$ node a → report a (position 0).
   • char b: $\delta (\text{a},b)$: node a ka koi child b nahi; $\text{fail}[a]=\text{root}$ follow karo; root ka child b hai → node b → report b (position 1).

Verify: ab pe total matches $=2$ (a at index 0, b at index 1); "" pe $=0$. Har length-1 pattern exactly ek baar match hua — ab mein ek a aur ek b hone ke saath consistent. ✓

---

Example 2 — Miss at the root (C3)

Forecast: leading x kuch match nahi karta — kya machine cleanly reset ho jaati hai, ya confuse ho jaati hai?

Steps.

1. Trie: root → c → ca → cat(✓cat).
2. char x: root ka koi child x nahi. Rule: $\delta (\text{root},x)=\text{root}$. Yeh step kyun? Root apna failure sink hai; root se koi edge na hone wala char hamesha hume root pe rakhta hai — koi progress lost nahi kyunki thi hi nahi.
3. char c: $\delta (\text{root},c)=$ node c. Yeh step kyun? Real edge exist karti hai, toh hum use lete hain.
4. char a: c→ca. char t: ca→cat → report cat (ends at index 3).

Verify: cat xcat mein ek baar milta hai, index 3 pe ending (0-based). Junk prefix x ne kuch cost nahi kiya — exactly ek match reported. ✓

---

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

Forecast: kis single character pe do words ek saath fire karte hain?

Steps.

1. Trie strings: h, he(✓), her, hers(✓), s, sh, she(✓), hi, his(✓). Yeh step kyun? Hume tree chahiye taaki failure links ko kuch point karne ki jagah mile.
2. Key failure link: she ka longest proper suffix jo trie node hai woh he hai, toh $\text{fail}[\text{she}]=\text{he}$. Yeh step kyun? Yahi rope hai jo ek landing ko do words report karne deti hai: he terminal hai aur she ki dictionary chain pe baitha hai.
3. u s h e r s scan karo (figure dekho — coloured path follow karo):

   char	state	reports
   u	root	–
   s	s	–
   h	sh	–
   e	she	she, he
   r	her	–
   s	hers	hers
   e pe double report kyun? she (terminal) pe land karke hum iska dictionary link he (bhi terminal) pe walk karte hain → dono fire karte hain. Yahi cell C5 hai.

4. r ne root se restart kyun nahi kiya (C6 preview): node she ka koi child r nahi; $\delta (\text{she},r)$ $\text{fail}[\text{she}]=\text{he}$ follow karta hai, aur he ka child r hai → her. Progress preserved.

Verify: ushers pe matches = she (index 1–3), he (index 2–3), hers (index 2–5): total 3 matches. Nesting: he hers ke region ke andar reported, she/he index 3 pe endpoint share karte hain. ✓

---

Example 4 — Deep failure jump (C6)

Forecast: abcd spell karne ke baad, agar agla char x hota, toh hum kitne levels drop karte?

Steps.

1. Trie: ek lamba branch a→ab→abc→abcd(✓), plus branches b→bc→bcd(✓), c→cd(✓), d(✓).
2. Failure links (har ek same suffix pe point karta hai ek letter chota): $\text{fail}[abcd]=bcd$, $\text{fail}[bcd]=cd$, $\text{fail}[cd]=d$, $\text{fail}[d]=\text{root}$. Yeh step kyun? Kyunki bcd abcd ka longest proper suffix hai jo ek node hai, aur neeche bhi aise hi.
3. abcd scan karo: hum seedha lambe branch se neeche chalte hain. Final node abcd pe hum abcd report karte hain, phir dictionary chain abcd → bcd → cd → d follow karte hain — charo patterns yahan khatam hote hain! Yeh step kyun? Har chota pattern same index pe khatam hone wala suffix hai, toh sab ek dictionary chain pe rehte hain.
4. Deep jump. Mano ek aur char x aata hai. $\delta (abcd,x)$: koi edge nahi; $\text{fail}[abcd]=bcd$ try karo (koi x nahi), phir cd (nahi), phir d (nahi), phir root (nahi) → root pe land karo. Hum 4 levels ek query step mein chade — lekin yeh cost build time mein amortised ho jaati hai.

Verify: abcd pe matches = {abcd, bcd, cd, d}, total 4, sab index 3 pe ending. ✓

---

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

Forecast: kaun sa single character ek saath do reports deta hai?

Steps.

1. Trie: a(✓)→ab(✓), b→bc(✓), c(✓).
2. Failure links: $\text{fail}[ab]=b$ (ab ka longest proper suffix jo node hai woh b hai), $\text{fail}[bc]=c$ (suffix c ek node & terminal hai). Yeh step kyun? $\text{fail}[bc]=c$ exactly wahi rope hai jo do matches chain karegi.
3. a b c scan karo:
   • a: node a → report a.
   • b: node ab → report ab.
   • c: $\delta (ab,c)$: ab ka koi c nahi; $\text{fail}[ab]=b$; b ka child c hai → node bc → report bc, phir dictionary link $\text{fail}[bc]=c$ (terminal) → report c. Yeh step kyun? Ek state (bc) do reports trigger karta hai (bc, c) — yahi cell C7 hai. Terminal flag pe kabhi mat ruko; hamesha chain walk karo.

Verify: abc pe matches = a(idx0), ab(idx0–1), bc(idx1–2), c(idx2): total 4. Index 2 pe c sirf bc se output link follow karke mila. ✓

---

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

Forecast: char as — kya answer 2 hai (non-overlapping) ya 3 (overlapping)?

Steps.

1. Trie: root → a → aa(✓aa). Failure links: $\text{fail}[a]=\text{root}$, $\text{fail}[aa]=a$. Yeh step kyun? aa ka longest proper suffix a hai, jo ek node hai — yeh rope har match ke baad ek a ki progress rakhti hai.
2. a a a a scan karo:
   • idx0 a: node a, koi report nahi.
   • idx1 a: a→aa → report aa (ends idx1).
   • idx2 a: $\delta (aa,a)$: aa ka koi child a nahi; $\text{fail}[aa]=a$; a→aa → report aa (ends idx2).
   • idx3 a: same fall-back → aa (ends idx3). Yeh step kyun? Failure link $\text{fail}[aa]=a$ matlab match ke baad bhi hume ek trailing a "yaad" rehta hai, toh agla a ek overlapping copy complete karta hai. Aho-Corasick overlapping matches automatically report karta hai.

Verify: aaaa mein aa ke occurrences (overlapping) = ending indices {1, 2, 3} pe → 3 matches. ✓

---

Example 7 — Real-world word problem (C9)

Forecast: kya badman apne aap ek hit count hoga aur phir bhi bad/mad uske andar count honge?

Steps.

1. Trie: b→ba→bad(✓bad)→badm→badma→badman(✓badman), aur m→ma→mad(✓mad).
2. Failure links jo matter karte hain:
   • $\text{fail}[badm]=m$ (suffix m ek node hai).
   • $\text{fail}[badman]=$ badman ka longest proper suffix jo ek node hai; man koi pattern-prefix nahi, an,n koi nodes nahi → $\text{fail}[badman]=\text{root}$. Yeh step kyun? Hume jaanna hai ki badm... kahan fall back karta hai taaki mad andar badm catch ho sake.
3. b a d m a d b a d m a n scan karo (indices 0..11):
   • idx2 d: node bad → bad.
   • idx3 m: node badm (real edge, bad→m exist karta hai).
   • idx4 a: badm→badma.
   • idx5 d: badma→ koi child d nahi? Path badma ka sirf child n hai. $\delta (badma,d)$: $\text{fail}[badma]=ma$ (suffix ma ek node hai), ma ka child d hai → node mad → mad. Yeh step kyun? badm... branch se rope hume mad branch mein land karti hai — ek embedded word catch karte hue.
   • idx6 b…idx8 d: bad rebuild karo → bad (doosra wala).
   • idx9 m→idx11 n: badm badma badman continue karo → idx11 pe node badman → badman.
4. Total reports. bad (idx0–2), mad (idx3–5), bad (idx6–8), badman (idx6–11). Yeh step kyun? badman apne aap report karta hai; uske andar bad prefix already idx8 pe report ho chuka tha — nested matches sab count hote hain.

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: kya failure link kabhi apne target string ki length se neeche point karta hai?

Steps.

1. Definition recall. $\text{fail}[v]$ woh node hai jiska string equal hai $\text{str}(v)$ ke longest proper suffix ke. Yeh kabhi us node ka child nahi hota — child lamba hoga, "suffix" ko contradict karta hua. Yeh step kyun? Yahi parent ki mistake list ka exact trap hai ("failure links go to a child of the suffix node"). Hum ise test karte hain.
2. Compute. $\text{str}(ab)=$ ab. Iske proper suffixes hain b aur `` (empty). Jo longest trie node hai woh b hai. Toh $\text{fail}[ab]=$ node b itself. Yeh step kyun? Seedha definition match karo, intuition-trap nahi.
3. Verdict. Claim FALSE hai. $\text{fail}[ab]=$ node b, jiska depth 1 hai (ab ke depth 2 se chota). Failure link hamesha upar ya sideways strictly shorter depth ki taraf point karta hai, kabhi deeper child ki taraf nahi.

Verify: $\text{fail}[ab]$ ki depth = 1 < ab ki depth = 2, aur $\text{str}(\text{fail}[ab])=$b ab ka proper suffix hai. Definition ki dono conditions hold karti hain; "child" claim depth inequality violate karta hai. ✓

---

Recall Humne kaun se cells cover kiye?

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 — woh failure function jise yeh generalize karta hai.
• Trie — prefix tree — woh skeleton jise hum drive karte rahe.
• BFS — breadth-first search — woh order jisne failure links computable banaye.
• Finite Automata — DFA/NFA — completed $\delta$ table hai kya.
• Z-algorithm and string matching, Suffix Automaton, Suffix Tree — cousins doosre string tasks ke liye.