Aho-Corasick — multiple pattern search, automaton

HOW to build it — derivation from scratch

Step 1 — Insert patterns into the trie

For each pattern, walk from root, creating child nodes for new characters. Mark the final node as a terminal for that pattern. This is just merging shared prefixes.

Step 2 — Compute failure links by BFS

Derivation of the failure rule. Let node $v$ have parent $p$ via character $c$ (so $\text{str}(v)=\text{str}(p)+c$ ). We want the longest proper suffix of $\text{str}(v)$ that is a trie node.

A proper suffix of $\text{str}(v)$ ending in $c$ has the form $s + c$ where $s$ is a proper suffix of $\text{str}(p)$ .
The longest such $s$ that is a node, followed by $c$ , is what we need.
The candidates "longest proper suffix of $p$ that is a node" are exactly $\text{fail}[p]$ , then $\text{fail}[\text{fail}[p]]$ , … (the failure chain of $p$ ).

So:

\text{fail}[v] = \text{go}\big(\, \text{first node } u \text{ in } \{\text{fail}[p], \text{fail}^2[p], \dots\} \text{ that has a child on } c\,,\; c\big)

and if none has a child on $c$ , then $\text{fail}[v] = \text{root}$ . Root's children have $\text{fail} = \text{root}$ .

Step 3 — Build the automaton (lazy → full transitions)

To avoid chasing the failure chain at query time, precompute a complete transition $\delta$ :

\delta(v,c) = \begin{cases} \text{child}(v,c) & \text{if } v \text{ has a real edge on } c\\[4pt] \delta(\text{fail}[v],\, c) & \text{otherwise} \end{cases}

with $\delta(\text{root},c)=\text{root}$ if root has no child on $c$ . Computed during the same BFS, this makes every step $O(1)$ .

Step 4 — Scan the text

Start at root. For each text char $c$ : state = δ(state, c); then report all patterns via state's output (dictionary) links.

Figure — Aho-Corasick — multiple pattern search, automaton

Worked Example 1 — patterns {he, she, his, hers}

Text: ushers

Trie (strings at nodes): h, he(✓he), her, hers(✓hers), s, sh, she(✓she), hi, his(✓his).

Key failure links:

fail[she] = he? No — longest proper suffix of "she" that's a node is "he". ✓ So fail[she]=he, and since he is terminal, scanning "she" also reports "he".

Scan u s h e r s:

char	state	reports	Why this step?
u	root	–	no edge `u`, δ(root,u)=root
s	s	–	root has child `s`
h	sh	–	`s`→`h` edge exists
e	she	she, he	`sh`→`e`; output of `she` + via fail `he`
r	her	–	δ(she,r): she has no `r`; follow fail→he, he→r=her
s	hers	hers	her→s = hers (terminal)

Worked Example 2 — patterns {a, ab, bab, bc, bca, c, caa}

Why this is interesting: overlapping outputs. Scanning text abccab:

a → reports a
b → node ab, reports ab
c → δ(ab,c): ab has no c; fail[ab]=b, b→c=bc, reports bc; also fail of bc may give c → reports c
continuing finds c again, etc.

Common mistakes

Recall Feynman: explain to a 12-year-old

You have a list of forbidden words and a giant book. You want to find every forbidden word fast. First, write all the words into a shared "word tree" so words that start the same (like "he" and "hers") share branches. Then add shortcut ropes: if you were spelling "she" and the next letter doesn't fit, instead of going back to the very start, a rope drops you to "he" — because "he" is the longest tail of "she" that's still the start of a word. Now you just slide one finger through the book letter by letter, following branches or shortcut ropes, and every time you land on a marked spot you shout the matched words. One pass, all words, done.

Flashcards

What problem does Aho-Corasick solve?

Find all occurrences of many patterns in a text in a single pass,

O(n + M + z)

What is a failure link of node v?

The node equal to the longest proper suffix of str(v) that is also a trie node (a prefix of some pattern).

Why are failure links computed in BFS order?

fail[v] points to a strictly shorter string (smaller depth), so all needed fail values are ready when processing by increasing depth.

What is the goto/transition δ(v,c) when v has no real edge on c?

δ(fail[v], c) — recurse to the failure link's transition (root if all fail).

Why must you follow dictionary (output) links, not just check the terminal flag?

A shorter pattern can end as a suffix at the same position (e.g. "he" inside "she"); those matches live on the failure chain.

Query time complexity (with full transition table)?

O(n + z): one O(1) lookup per char plus output of z matches; independent of number of patterns.

Build time/space with explicit transition table?

O(M·Σ), where M = total pattern length, Σ = alphabet size.

Failure-link rule for str(v)=str(p)+c?

Walk fail chain of parent p; first ancestor u with a child on c gives fail[v]=child(u,c); else root.

What does a node in the trie represent?

A prefix shared by one or more patterns; the path of chars from root spells it.

How is Aho-Corasick related to KMP?

It generalizes KMP's prefix-function/failure-function from a single string to a trie of many strings.

Connections

KMP — single pattern matching (failure function = special case on a path)
Trie — prefix tree (the skeleton structure)
Suffix Automaton / Suffix Tree (different multi-substring machines)
Finite Automata — DFA/NFA (Aho-Corasick is a DFA over patterns)
Z-algorithm and string matching
BFS — breadth-first search (used to build failure links)

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Socho tumhe ek lambi text me bahut saare words (dictionary) ek saath dhoondhne hain. Har word ke liye alag KMP chalana slow hai. Aho-Corasick ka idea simple hai: pehle saare patterns ka ek trie (prefix tree) banao, taaki "he" aur "hers" jaise same shuruaat waale words branch share karein. Phir har node pe ek failure link lagao — yeh KMP ke failure function ka hi multi-pattern version hai. Failure link bolta hai: "agle character pe match fail ho gaya, toh poora root pe wapas mat jao; bas utna jump karo jahan tak ka tail abhi bhi kisi pattern ka prefix hai."

Failure link ka exact rule: agar node v ka string = str(parent)+c hai, toh parent ke failure chain pe chalo, jo pehla node c pe child rakhta hai — uska child hi fail[v] hai; nahi mila toh root. In links ko BFS (depth-wise) se banate hain kyunki failure hamesha chhote (kam length waale) string ko point karta hai, jo pehle ready ho jaata hai.

Phir hum ek transition table δ(v,c) precompute kar lete hain: agar real edge hai toh wahi, warna δ(fail[v],c). Isse text scan karte waqt har character bas O(1) lookup banta hai. Total query time O(n + z) — yaani patterns kitne bhi ho, scan ka time same! Sirf ek dhyaan: match report karte waqt sirf current node ka terminal flag mat dekho — dictionary/output links ki chain follow karo, kyunki chhota pattern bade pattern ke andar suffix banke same position pe khatam ho sakta hai (jaise "she" me "he").

Yeh cheez real life me kaam aati hai: spam/keyword filtering, virus signature scanning, DNA me multiple motifs dhoondhna, search highlighting. Ek hi machine, ek hi pass — bahut efficient.

Aho-Corasick — multiple pattern search, automaton

WHY does this work?

WHAT are the pieces?

HOW to build it — derivation from scratch

Step 1 — Insert patterns into the trie

Step 2 — Compute failure links by BFS

Step 3 — Build the automaton (lazy → full transitions)

Step 4 — Scan the text

Complexity

Worked Example 1 — patterns {he, she, his, hers}

Worked Example 2 — patterns {a, ab, bab, bc, bca, c, caa}

Common mistakes

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — String Algorithms

Connections