Home▸Algorithms & AI▸Aho–Corasick — Multi-Pattern String Search

🔤 Aho–Corasick — Multi-Pattern String Search

Build a trie of several patterns plus failure links, then scan text in a single O(n) pass, watching the automaton follow failure links and report every match at once.

Algorithms & AI2DAdvanced60 FPS

About Aho–Corasick

The Aho–Corasick algorithm, invented in 1975 by Alfred V. Aho and Margaret J. Corasick at Bell Laboratories, solves the multi-pattern string matching problem: given a dictionary of patterns and a text, find every occurrence of every pattern in a single linear pass. It generalizes the Knuth–Morris–Pratt (KMP) algorithm from one pattern to many by merging all patterns into a shared trie and computing failure links with a breadth-first traversal, exactly as KMP computes a failure function for a single pattern. Each node's failure link points to the longest proper suffix of its string that is also a prefix of some pattern, and each node carries a merged "dictionary suffix" output set gathered by following failure links up to the root. Scanning a text of length n then costs only O(n + m + z), where m is the combined pattern length and z the number of matches reported. Because of this efficiency, Aho–Corasick underlies the original fgrep/grep -F utility, antivirus signature scanners that check files against thousands of malware signatures at once, and network intrusion detection systems that inspect packet payloads for known attack strings in real time.

Frequently Asked Questions

How is Aho–Corasick different from just running KMP once per pattern?

Running KMP separately for k patterns over a text of length n costs O(k·n) in the worst case, since each pattern requires its own pass. Aho–Corasick merges all patterns into one automaton and scans the text exactly once, costing O(n + m + z) regardless of how many patterns there are, which is far faster when searching for hundreds or thousands of patterns simultaneously.

What exactly is a failure link, and why is it needed?

A failure link from node v points to the trie node representing the longest proper suffix of v's string that is still a prefix of some pattern. When the automaton can't extend the current match with the next character, it follows failure links instead of restarting from the root, so no input character is ever re-read — this is what keeps the scan linear in the text length.

Can Aho–Corasick find overlapping matches, like both "he" and "hers" ending near the same position?

Yes. Because each trie node stores a merged output set gathered by following failure links up to the root (the dictionary suffix chain), a single state can report multiple patterns that are suffixes of one another or that simply end at the same text position, so all overlapping and nested matches are reported correctly.

Where is Aho–Corasick used in practice?

Beyond its original use in the Unix fgrep utility, it powers antivirus engines matching files against large signature databases, network intrusion detection systems scanning packets for known attack strings, spam and content filters, and bioinformatics tools searching DNA sequences for many short motifs at once.

⚙ Under the hood

Build a trie of several patterns plus failure links, then scan text in a single O(n) pass, watching the automaton follow failure links and report every match at once.

algorithmsstring matchingtrieautomatoncomputer science

2D · HTML5 Canvas 2D · 60 FPS target · runs fully client-side, no install