Aho-Corasick — multiple pattern search, automaton: Exercises

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

Ek chhota sa vocabulary reminder jo tum use karoge, plain words mein:

Definition Words jo hum reuse karenge (sab yahan defined hain, parent se match karte hain)

str(v) — woh string jo tum root se node $v$ tak walk karke spell karte ho.
depth(v) — str(v) mein characters ki count, yaani $depth (v) = ∣ str (v) ∣$ . Root ki depth $0$ hoti hai; har downward edge ek character add karta hai, isliye depth exactly $1$ per level badhti hai.
fail[v] — woh node jiska string, str(v) ka longest proper suffix hai jo trie mein bhi ek node hai (kisi pattern ka prefix). "Proper" matlab str(v) se chhota.
δ(v, c) — automaton transition: node $v$ se character $c$ padhne ke baad tum kahan pohonchte ho, failure links follow karte hue agar real edge nahi hai.
output / dictionary chain — $v \to fail [v] \to fail [fail [v]] \to \dots$ walk karna aur har terminal node ko report karna, kyunki har ek us same text position par end hone wala ek chhota pattern hai.
dictLink[v] — ek shortcut pointer: failure chain par $v$ ke strictly upar nearest terminal node (yaani $fail [v], fail^{2} [v], \dots$ follow karte hue mila pehla terminal), ya "none" agar us chain par koi terminal nahi hai. Yeh tumhe har intermediate node climb karne ki jagah seedha ek match se doosre par jump karne deta hai.

Related tools jo tum doosre tab mein open rakhna chahoge: Trie — prefix tree, KMP — single pattern matching, BFS — breadth-first search, Finite Automata — DFA/NFA.

Level 1 — Recognition

L1.1

In ek-ek sentence mein batao ki yeh chaar objects kya hain: str(v), fail[v], δ(v,c), dictionary chain.

Recall Solution

str(v): root se $v$ tak spell ki gayi string.
fail[v]: str(v) ke longest proper suffix ka node, jo ab bhi ek node hai (ek pattern prefix).
δ(v,c): c padhne par tum kahan jaate ho — real child agar exist kare, warna δ(fail[v], c).
Dictionary chain: $v$ se fail links follow karke mile terminal nodes ka sequence; sab yahan ek match report karte hain.

L1.2

Patterns {he, she, his, hers}. Batao ki yeh strings trie mein node hain ya nahi: h, sh, her, hi, sha, e?

Recall Solution

Ek string node hai iff woh kisi pattern ka prefix hai.

h ✓ (he, his, hers ka prefix)
sh ✓ (she ka prefix)
her ✓ (hers ka prefix)
hi ✓ (his ka prefix)
sha ✗ (koi pattern sha se start nahi hota)
e ✗ (koi pattern e se start nahi hota; note karo ki "e" "he" mein appear karta hai lekin woh prefix nahi hai)

Level 2 — Application

L2.1

Patterns {a, ab, bab, bc, bca, c, caa}. fail[bab] ko haath se compute karo, failure-chain search dikhate hue.

Recall Solution

str(bab) = "bab", parent p = ba character b ke zariye. Hum "bab" ka longest proper suffix dhundh rahe hain jo ek node ho. Last char b par end hone wale proper suffixes: "ab", "b", "". Parent p = ba ki failure chain walk karo, b par child dhundhte hue:

fail[ba] = "ba" ka longest proper suffix jo node hai = "a" (node ✓). Kya node a ka b par child hai? Haan: a → ab. Roko.
Toh fail[bab] = ab. Check karo: "ab" actually "bab" ka longest proper suffix hai jo node hai. ✓

L2.2

Same patterns. Text abcc ke liye scan table fill karo. Saare matches report karo, aur har character ke liye batao ki kyun tum wahan gaye jahan gaye.

Recall Solution

char	state after	reports	why
a	`a`	a	kyunki root ka `a` par real edge hai; `a` terminal hai
b	`ab`	ab	kyunki `a` ka `b` par real edge hai; `ab` terminal hai
c	`bc`	bc, c	kyunki `ab` ka `c` par real edge nahi, toh δ(ab,c)=δ(fail[ab]=b, c); `b` ka real edge `c` → `bc`; dictLink[bc]=c se `c` fire hota hai
c	`c`	c	kyunki `bc` ka `c` par real edge nahi, toh δ(bc,c)=δ(fail[bc]=c, c); `c` ka `c` edge nahi, toh δ(c,c)=δ(fail[c]=root, c)=root child `c`=`c`; `c` terminal hai

Matches (end position ke hisaab se grouped, ek position mein longest-first): a (pos 1), ab (pos 2), bc, c (pos 3), c (pos 4).

L2.3

Text abcc mein, teesre character (c) ne ek single state se do patterns kyun report kiye?

Recall Solution

Node bc (jo terminal hai) par land karne ke baad, dictionary chain hai: bc → fail[bc] = c → fail[c] = root. Node c bhi terminal hai, toh woh bhi fire karta hai. Dono patterns us same text position par end hote hain, ek doosre ka suffix hote hue. dictLink[bc] shortcut bc se seedha c par point karta hai, jisse hum dono emit kar sakte hain bina non-terminal nodes visit kiye.

Level 3 — Analysis

L3.1

Prove karo ki fail[v] hamesha $v$ se strictly smaller depth wale node ko point karta hai. Yeh ek fact BFS ordering ko justify kyun karta hai?

Recall Solution

Yaad karo $depth (v) = ∣ str (v) ∣$ (is page ke top par defined hai): root se $v$ tak spell ki gayi string mein characters ki count. Ab fail[v], str(v) ka proper suffix hai, toh $∣ str (fail [v]) ∣ < ∣ str (v) ∣$ , isliye $depth (fail [v]) < depth (v)$ — strictly smaller. Isliye jab BFS depth $d$ par pohonchta hai, depth $< d$ ke har node (jinmein saare fail targets shamil hain jinki zaroorat hai) already finalize ho chuke hain. Exactly yahi wajah hai ki hum fail ko breadth-first order mein compute karte hain, recursively nahi.

L3.2

Parent claim karta hai ki scanning $O (n + z)$ cost karta hai jahan $z$ = reported matches ki count. "Potential argument" explain karo: poore scan mein failure-chain walking ki total cost kyun nahi badhti, bhale hi ek single step kaafi links jump kare?

Recall Solution

Ek potential define karo = current state ki $depth$ . Ek text character padhna depth ko zyada se zyada $1$ badhata hai (ek downward edge), toh $n$ characters mein depth total zyada se zyada $n$ badhti hai. Har failure jump depth ko kam se kam $1$ ghatata hai. Kyunki depth $0$ se shuru hoti hai, $\geq 0$ rehti hai, aur total sirf $n$ baar badhti hai, poore scan mein failure jumps ki count $\leq n$ hai. Isliye saara jumping amortized $O (n)$ hai — kisi single step ki cost matter nahi karti, sirf total matter karta hai. (Full δ table ke saath har character aur bhi simple hai: ek $O (1)$ lookup.) Extra $z$ unavoidable hai: tumhe $z$ matches emit karne mein waqt toh lagana hi padega.

L3.3

Patterns {he, she, his, hers}. Ek student claim karta hai ki fail[hers] = s. Kya yeh sahi hai? Agar nahi, toh sahi jawab reasoning ke saath do.

Recall Solution

str(hers) = "hers". "hers" ka longest proper suffix jo ek node ho: "ers" check karo (✗), "rs" (✗), "s" (✓ node). Koi longer suffix jo node ho? "ers", "rs" kisi bhi pattern ke prefix nahi hain. Toh fail[hers] = s. Student sahi hai. (Trap defused: bahut log zyada fancy target expect karte hain, lekin s genuinely yahan longest matching suffix hai.)

Level 4 — Synthesis

L4.1

Patterns {ab, bab, ba} ke liye automaton scratch se banao: saare nodes list karo, har node ke liye fail[v] do, phir failure links draw karo.

Neeche figure finished automaton dikhata hai jisse tum khud check kar sako: solid teal arrows trie edges hain (har ek ek character add karta hai, neeche greater depth ki taraf jaata hai), dashed plum arrows failure links hain (har ek upar strictly shorter suffix ko point karta hai), aur orange nodes terminals hain jahan ek pattern end hota hai. Visually notice karo ki har plum arrow ek shallower node ko rise karta hai — L3.1 ka depth-strictly-decreases fact concrete ho gaya.

Figure — Aho-Corasick — multiple pattern search, automaton

Recall Solution

Nodes (strings ke roop mein): root, a, ab(✓ab), b, ba(✓ba), bab(✓bab). BFS mein fail compute karo (increasing depth):

depth 1: fail[a]=root, fail[b]=root (root ke children root par fail hote hain).
depth 2:
- fail[ab]: parent a, char b. fail[a]=root walk karo; root ka child b par? haan b. Toh fail[ab]=b.
- fail[ba]: parent b, char a. fail[b]=root walk karo; root ka child a par? haan a. Toh fail[ba]=a.
depth 3:
- fail[bab]: parent ba, char b. fail[ba]=a walk karo; node a ka child b par? haan ab. Toh fail[bab]=ab. Yeh upar figure mein plum arrows se match karta hai.

L4.2

L4.1 ke automaton ko use karke text babab scan karo aur har transition ki reason ke saath har match report karo.

Recall Solution

char	state	reports	why
b	`b`	–	kyunki root ka `b` par real edge hai
a	`ba`	ba	kyunki `b` ka `a` par real edge hai; `ba` terminal hai
b	`bab`	bab, ab	kyunki `ba` ka `b` par real edge hai → `bab` terminal; dictLink[bab]=ab se `ab` fire hota hai
a	`ba`	ba	kyunki `bab` ka `a` par real edge nahi, toh δ(bab,a)=δ(fail[bab]=ab, a); `ab` ka `a` edge nahi, toh =δ(fail[ab]=b, a); `b` ka real edge `a` → `ba` terminal hai
b	`bab`	bab, ab	kyunki `ba` ka `b` par real edge hai → `bab` terminal; dictLink[bab]=ab se `ab` fire hota hai

Matches end position ke hisaab se grouped (longest-first): ba(pos 2), bab, ab(pos 3), ba(pos 4), bab, ab(pos 5).

L4.3

Aisi patterns design karo (kam se kam teen) jisme kisi node ki dictionary chain ek position par teen patterns report kare. Patterns aur position do.

Recall Solution

Lo {c, bc, abc}. Text abc scan karo.

a → node a (koi report nahi), kyunki root ka real edge a hai
b → ab? real edge exist karta hai → ab (koi report nahi)
c → abc (✓abc), kyunki ab ka real edge c hai. Dictionary chain: abc → fail = bc (✓) → fail = c (✓) → root. Final c par, teen patterns fire hote hain: abc, bc, c — har ek pichle ka suffix. Position: index 3 (last char).

Level 5 — Mastery

L5.1

Tumhare paas $m$ patterns hain jinka total length $M$ hai, alphabet size $Σ$ hai, aur $z$ total matches wala length $n$ ka text hai. Ek colleague propose karta hai: "bas KMP ek baar har pattern ke liye run karo." Dono costs batao aur ek precise inequality do jab Aho-Corasick asymptotically cheaper ho.

Recall Solution

KMP-per-pattern total cost: $O (M + m n + z)$ — saare prefix functions build karna $O (M)$ hai, $m$ patterns mein se har ek poora text scan karta hai ( $m n$ ), plus $z$ report karna.
Aho-Corasick: build $O (M Σ)$ (full table), scan $O (n + z)$ ; total $O (M Σ + n + z)$ . Precise criterion. Aho-Corasick asymptotically cheaper tab hoga jab uska total smaller ho: $M Σ + n + z < M + m n + z ⟺ M Σ + n < M + m n .$ Rearrange karne par ( $z$ terms cancel ho jaate hain): $M (Σ - 1) < (m - 1) n ⟺ n > \frac{M ( Σ - 1 )}{m - 1} (for m \geq 2) .$ Toh kisi bhi $m \geq 2$ ke liye, Aho-Corasick tab jeet jaata hai jab text $\frac{M ( Σ - 1 )}{m - 1}$ se longer ho. Jaise-jaise $m$ badhta hai yeh threshold shrink hoti hai, aur maps ke saath (build $O (M)$ , toh $M Σ$ term $M$ ban jaata hai) condition relax hokar simply $n > 0$ ho jaati hai jab bhi $m \geq 2$ ho.

L5.2

Amortized bound prove karo: poore scan mein, outputs emit karne ke liye use hone wale failure-link hops ki total count $O (n + z)$ hai sirf tabhi agar tum dictLink use karo; naively yeh $ω (n)$ ho sakta hai. Ek aisi family of inputs do jahan naive output-walk quadratic ho.

Recall Solution

Naive quadratic family: patterns {a, aa, aaa, …, a^k} (aⁿ ke saare prefixes), text aⁿ. Text position $i$ par, state node a^i hai, aur uski failure chain hai a^i → a^{i-1} → … → a → root. Outputs emit karne ke liye naive walk chain ke har node ko visit karta hai, position $i$ par $Θ (i)$ cost lagti hai, aur $\sum_{i = 1}^{n} i = Θ (n^{2})$ — quadratic. dictLink fix: dictLink[v] = failure chain par $v$ ke strictly upar nearest terminal node. Emit karna phir sirf ek reported match se doosre terminal tak hop karta hai, toh emit work matches ki count $z$ ke proportional hai plus $O (1)$ per character, giving $O (n + z)$ . Key: output ke dauran kabhi bhi non-terminal node mat touch karo.

L5.3

Full construction challenge. Patterns {ab, ba, bab, aba}, alphabet {a,b}. (a) Nodes aur fail list karo. (b) Saare nodes aur dono characters ke liye full transition table $δ (v, c)$ compute karo, har cell justify karte hue. (c) ababa scan karo aur matches list karo.

Recall Solution

(a) Nodes: root, a, ab(✓ab), aba(✓aba), b, ba(✓ba), bab(✓bab). Fail (BFS):

fail[a]=root, fail[b]=root
fail[ab]: parent a,b; fail[a]=root, root child b → fail[ab]=b
fail[ba]: parent b,a; fail[b]=root, root child a → fail[ba]=a
fail[aba]: parent ab,a; fail[ab]=b, b child a? haan ba → fail[aba]=ba
fail[bab]: parent ba,b; fail[ba]=a, a child b? haan ab → fail[bab]=ab

(b) Full δ — har cell batata hai ki real edge exist karta hai ya nahi, warna fail se recurse karta hai:

node	δ(·,a)	why	δ(·,b)	why
root	a	real edge root→a	b	real edge root→b
a	a	real edge nahi; δ(fail[a]=root,a)=a	ab	real edge a→b
ab	aba	real edge ab→a	b	real edge nahi; δ(fail[ab]=b,b)=b (b ka b-edge nahi, δ(root,b)=b)
aba	a	real edge nahi; δ(fail[aba]=ba,a): ba ka a-edge nahi, δ(fail[ba]=a,a)=a	bab	real edge nahi; δ(fail[aba]=ba,b)=bab (ba ka real edge b→bab hai)
b	ba	real edge b→a	b	real edge nahi; δ(fail[b]=root,b)=b
ba	a	real edge nahi; δ(fail[ba]=a,a)=a	bab	real edge ba→b
bab	aba	real edge nahi; δ(fail[bab]=ab,a)=aba (ab ka real edge a hai)	b	real edge nahi; δ(fail[bab]=ab,b)=b

(c) Scan ababa (full δ table use karke):

a: root→a. reports: none.
b: a real edge b → ab. reports: ab.
a: ab real edge a → aba. reports aba; dictLink[aba]=ba → ba.
b: aba ka b-edge nahi → δ(aba,b)=bab. reports bab; dictLink[bab]=ab → ab.
a: bab ka a-edge nahi → δ(bab,a)=aba. reports aba; dictLink[aba]=ba → ba.

Matches end position ke hisaab se grouped (longest-first): ab(pos 2), aba, ba(pos 3), bab, ab(pos 4), aba, ba(pos 5).

Recall Self-test checklist (sirf khatam karne ke baad kholna)

Kya tumne, har problem ke liye, (1) confirm kiya ki har claimed node real prefix hai, (2) verify kiya ki $depth (fail [v]) < depth (v)$ , (3) output ke liye sirf terminal flag se nahi balki dictionary chain (ya dictLink) follow ki, aur (4) fail/δ BFS order mein build kiya? Agar haan, toh tumne mechanics master kar li hai.