Aho-Corasick multi-pattern matching

Find thousands of patterns in ONE pass. KMP with a trie. Search cost independent of how many patterns.

Three layers

• Trie: all patterns in a prefix tree (shared prefixes shared)
• Failure links: KMP's "where to resume" generalized to the tree
• Output links: one position reports every pattern ending there
• Feed the text through once; the pointer never rewinds → O(n + matches)

Watch the automaton scan

Dictionary {he, she, his, hers}, text 'ushers'. ◆ = pattern ends here. 'she' fires she + he (output link); 'r' follows a failure link to 'her'.

One pass vs k passes

Aho-Corasick: flat (one pass, any pattern count). 500 patterns → 260× fewer examinations.

Two things to get right

• Merge OUTPUT links along failures, or you miss 'he' inside 'she'
• Build failure links breadth-first (shallow first) — KMP's ordering dependency
• Fixed pattern set → changing patterns means rebuild
• Single pattern? Use KMP/Boyer-Moore instead

Takeaway

The tier's theme: precompute STRUCTURE before the scan to make matching cheap. KMP table · rolling hash · skip table · suffix index · this automaton — all the same move. Strings tier done. Next tier: the paradigms behind the algorithms.