Course contentsShow
← Computer Science
Lesson 839 of 2,87219. Searching and SelectionFree lesson

Multiple Pattern Matching: Aho-Corasick

Learn the Aho-Corasick algorithm using a trie with failure links to search for multiple patterns simultaneously in O(n+m+z) time.

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:

  1. A trie containing all your search patterns
  2. 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.