Multiple Pattern Matching: Aho-Corasick
What you'll learn: How to search for multiple patterns in a text simultaneously using the Aho-Corasick algorithm.
The Core Problem
You've learned algorithms like KMP and Boyer-Moore that find one pattern in a text efficiently. But what if you need to search for many patterns at once—say, hundreds of keywords in a document? Running KMP for each pattern separately would be wasteful.
How Aho-Corasick Works
The Aho-Corasick algorithm cleverly combines two data structures:
- A trie containing all your search patterns
- Failure links that jump to the longest proper suffix when a mismatch occurs
Think of it like autocorrect: as you type through the text, you're walking down the trie. When you hit a dead-end (no matching child), instead of starting over from the root, a failure link instantly teleports you to another position in the trie where a suffix of what you've seen continues. This way, you never re-examine characters.
The Algorithm Steps
Preprocessing:
- Build a trie from all patterns
- Add failure links using BFS (similar to KMP's prefix function, but across the entire trie)
- Mark output nodes (where patterns end)
Searching:
- Walk through the text character-by-character
- Follow trie edges when they match
- Follow failure links on mismatches
- Report matches at output nodes
Complexity
- Time: O(n + m + z) where n = text length, m = sum of pattern lengths, z = number of matches
- Space: O(m) for storing the trie and links
You scan the text once regardless of how many patterns you're searching for!
Key Takeaway: Aho-Corasick uses a trie with failure links to search for multiple patterns simultaneously in linear time, making it ideal for applications like virus scanning, spam filtering, and keyword highlighting.