Aho-Corasick — multiple pattern search, automaton: Question bank

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

True ya false — justify karo

Trie ka har node kam se kam ek pattern ka prefix represent karta hai.

True. Nodes sirf patterns insert karte waqt banaye jaate hain, aur har reached node exactly wahi string hoti hai jo root se spell hoti hai, jo construction ke hisaab se us pattern ka prefix hai jise insert kiya ja raha tha.

Failure link fail[v] ek aisi node ki taraf point kar sakta hai jo v se zyaada deep ho.

False. fail[v] str(v) ka sabse lamba proper suffix hai jo ek node hai, aur proper suffix strictly str(v) se chhota hota hai, isliye uski node ki depth strictly kam hogi.

fail[v] hamesha trie mein v ke ancestor ki taraf point karta hai.

False. Ye ek chhoti string ki taraf point karta hai, lekin woh string zaruri nahi ki v ke root path par ho. Jaise she aur he patterns ke saath, fail[she] hai he, jo ek alag branch par hai, she ka ancestor nahi.

Agar node v terminal hai, toh fail[v] follow karne par kabhi doosra terminal nahi milega.

False. Ek chhota pattern us jagah khatam hone wala suffix ho sakta hai — she terminal hai aur fail[she] = he bhi terminal hai, toh dono report hote hain.

Root ka failure link root khud hota hai.

True (convention se). Root empty string hai; uska koi proper suffix nahi jo ek chhoti node ho, isliye ye khud par loop karta hai, jisse fallback ka ek well-defined base case milta hai.

Root ke har child ka failure link root ke barabar hota hai.

True. Root ka child ek single character hota hai; uska sirf ek proper suffix hai — empty string — jiski node root hai, isliye fail = root.

Full transition table

δ

ke saath, text scan karte waqt query time mein failure chain follow karni pad sakti hai.

False.

δ

precompute karne ka yahi toh point hai ki failure chasing BFS build ke dauran absorb ho jaati hai, isliye har text character exactly ek

O (1)

table lookup hoti hai.

Aho-Corasick ki query time patterns ki sankhya par depend karti hai.

False. Query

O (n + z)

hai jahan

z

reported matches ki sankhya hai; patterns sab ek shared automaton mein build ke dauran bake ho jaate hain, har query par dobara scan nahi hote.

Agar do patterns identical hain, toh automaton break ho jaata hai.

False. Woh same trie path mein merge ho jaate hain aur terminal node simply dono (ya ek) pattern label carry karti hai; failure/transition logic ke baare mein kuch bhi nahi badalta.

Transition

δ (v, c)

wahi object hai jo goto edge go[v][c] hai.

False. go[v][c] ek real trie edge hai (exist nahi bhi kar sakta);

δ (v, c)

completed automaton transition hai jo real edge na hone par fail ke through fall back karta hai, isliye ye hamesha defined hota hai.

Error dhundho

"Main fail[v] compute karta hoon sirf fail[parent(v)] dekhkar; kabhi aage chain nahi karta."

Galat. Agar fail[parent] ke paas edge char c par koi child nahi hai, toh tumhe fail[fail[parent]] follow karna hoga, aur aage bhi, jab tak koi node ka c-child na mile ya root na aa jaaye. Ek hop par rukne se fail[v] bahut shallow ya galat node par point kar sakta hai.

"Main failure links compute karne ke liye nodes ko DFS (depth-first) se process karta hoon."

Galat ordering. fail[v] chhoti strings (kam depth) par depend kar sakta hai jo DFS ne abhi finish nahi ki hain. BFS guarantee karta hai ki strictly-chhoti saari nodes pehle done hain, isliye breadth-first by depth use karo.

"Har text position par main state.isTerminal check karta hoon aur tabhi report karta hoon jab woh true ho."

Incomplete. Chhote patterns jo suffixes ki tarah khatam hote hain woh dictionary/output chain par hote hain, current node ke flag par nahi. Sabko pakadne ke liye tumhe output links (ya precomputed dictLink) walk karne padte hain.

"fail[v] ko longest-suffix node ke ek child ki taraf point karna chahiye."

Ye fail ko goto se confuse karta hai. fail[v] woh node hai jo str(v) ke longest proper suffix ke barabar hai khud — ek completed string, ek character aage nahi.

"Jab c par koi real edge nahi hai toh main δ(v,c) = fail[v] set karta hoon."

Galat target. Rule hai δ(v,c) = δ(fail[v], c) — tum failure link par jump karte ho aur phir us node ka c par transition lete ho, jo khud aur aage fall back kar sakta hai. Sirf fail[v] par land karne se character c drop ho jaata hai.

"Kyunki KMP ek pattern ke liye

O (n)

hai, har pattern par KMP ek baar chalana basically Aho-Corasick jitna hi cost karta hai."

Galat. Per-pattern KMP ka cost

O (m \cdot n + M)

hota hai jahan

m

pattern count hai; Aho-Corasick

O (n + M + z)

hai, ek shared automaton se ek baar scan karke

m

factor hata deta hai.

"Maine trie aur failure links banaye lekin output/dictionary links skip kar diye — matches phir bhi theek report hote hain."

Sirf complete-node matches report hote hain; failure chain par suffix matches miss ho jaate hain. Har position par khatam hone wale saare patterns report karne ke liye output links (ya on-the-fly failure-chain walking) chahiye.

Why questions

Current state hamesha text ke abhi tak padhe gaye hisse ka sabse lamba pattern-prefix suffix kyun represent karta hai?

Kyunki

δ

jab possible ho real edge extend karta hai aur warna longest usable suffix par fall back karta hai; inductively ye state ko har step par maximal matched prefix par rakhta hai.

Hum mismatch par sirf root par restart kyun nahi kar sakte failure links ki jagah?

Restart karne se partially matched suffix throw ho jaata hai — she agla char par fail hone ke baad bhi he ek live match tha, aur restart karne se hers jaisa pattern miss ho jaata jo ussi se grow karta.

Scanning ke dauran total failure-chain traversal bounded kyun hai, amortized

O (1)

per char deta hai?

Har character "matched depth" ko zyaada se zyaada ek se push kar sakta hai upar, aur failure jumps sirf depth ghatate hain; total decreases

\leq

total increases

= n

, ek KMP-style potential argument. (Full

δ

ke saath ye cost poori tarah build mein shift ho jaati hai.)

Failure links un nodes ki taraf kyun point karni chahiye jo khud kisi pattern ke prefix hain?

Kyunki trie ka har node hai construction se kisi pattern ka prefix; fail[v] ek node ko target karta hai, isliye uski string automatically ek valid pattern-prefix hai — yahi use ek legal state banata hai jahan se continue kiya ja sake.

BFS order specifically (koi bhi topological order nahi) kyun kaafi hai?

fail[v] hamesha ek strictly chhoti string reference karta hai, aur trie mein depth string length ke barabar hoti hai, isliye increasing depth se order karna (exactly BFS) guarantee karta hai ki dependencies ready hain.

Build

O (M Σ)

kyun hai full transition table ke saath lekin

O (M)

hash maps ke saath?

Full table har node par har alphabet symbol ke liye ek transition store karta hai (

Σ

per node,

M

nodes); maps sirf real edges store karte hain, per-lookup hash cost ke trade par

O (M)

total space lete hain.

Ek state kabhi kabhi ek saath kai matches kyun trigger karta hai?

Output chain ek node ko chhote patterns se link karta hai jo uske suffix hain (jaise bc → c); ek single position kai nested patterns khatam kar sakta hai, isliye unhe sab emit karna zaroori hai.

Edge cases

Ek aisa text character ho jab root se koi edge match na kare toh kya hoga?

δ (root, c) = root

convention se; machine root par hi rehti hai aur simply char consume kar leti hai, kuch report nahi karti.

Agar ek pattern single character ka ho, jaise a?

Uska terminal node root ka direct child hai; har baar text mein a aata hai,

δ

wahan land karta hai (ya output chain us se pass hoti hai) aur a report hota hai.

Agar ek pattern doosre ka proper substring ho, jaise he andar hers?

he hers ke path par baith a hai; jab bhi matching he ke terminal node tak pahunche ya us se guzre — output links ke zariye bhi — he independently report hota hai chahe hers complete ho ya na ho.

Agar pattern set empty ho?

Trie sirf root hai har character par self-loop transitions ke saath; koi bhi text scan karte waqt har step par root par land karta hai aur kuch report nahi hota — ek valid, degenerate automaton.

Agar text empty ho?

Machine root par start hoti hai aur koi step nahi leti, toh zero matches; build cost phir bhi pay hoti hai lekin query trivially

O (0 + 0)

hai.

Agar do patterns apna poora prefix share karein lekin last char par differ karein, jaise cat aur car?

Woh path c → a share karte hain, phir do terminals cat aur car par branch karte hain; trie common prefix merge karta hai aur har ending distinct rehti hai.

Agar ek pattern text mein kai baar aaye (overlapping)?

Har occurrence alag se report hoti hai jab automaton corresponding state tak pahunchta hai; overlaps naturally handle hote hain kyunki state already har position par longest matched suffix encode kar leti hai.

Recall Aage badhne se pehle quick self-test

Fail vs goto ::: goto ek real trie edge hai; fail longest-proper-suffix node par jump hai. Terminal flag vs output chain ::: flag ek pattern yahan khatam hone ka mark hai; output chain yahan khatam hone wale saare chhote patterns dhundti hai. BFS kyun ::: fail hamesha ek chhoti string point karta hai, jo increasing depth se process karne par pehle ready hoti hai. Query cost ::: $O (n + z)$ , patterns ki sankhya se independent.