🕸️ Aho–Corasick
Multi-pattern string search automaton
State: 0 · Pos 0 / 0
Setup
Controls
Stats
Current state
0
Position
0 / 0
Matches
0
Trie nodes
0
Match log
No matches yet.
Info & Theory

Aho–Corasick finds every occurrence of several patterns in a text in one linear pass, by combining a trie of all patterns with failure links that generalize the idea behind the single-pattern KMP algorithm.

1. Trie construction

Insert every pattern into a shared trie rooted at node 0. Each node represents the string spelled out by the path from the root; a node is marked as an output node if that path equals one of the patterns.

2. Failure links (BFS)

For every node v reached from parent u via character c, the failure link f(v) points to the node representing the longest proper suffix of v's string that is also a prefix of some pattern (i.e. also a node in the trie). Failure links are computed with a BFS over the trie, level by level: root's children get f = root; for a deeper child reached from u via c, walk u's failure chain until a node with a goto edge on c is found (or fall back to root).

3. Output / dictionary suffix links

A node can represent a suffix of several matched patterns at once, so each node's effective match set is its own outputs plus all outputs reachable by following failure links up to the root — the dictionary suffix chain. Precomputing this merged set (or walking it live) lets the scanner report every pattern ending at a position without missing overlapping matches.

4. Scanning

Feed the text one character at a time. From the current state, follow a trie edge if one exists; otherwise repeatedly follow failure links until an edge is found or the root is reached. After each transition, report the merged output set at the new state as matches ending at that position.

Complexity

Building the trie and failure links costs O(m) where m is the total length of all patterns; scanning the text costs O(n) where n is the text length. Reporting all matches costs O(z) where z is the number of matches, giving a total of O(n + m + z).

About Aho–Corasick

Written by MySimulator Team · Reviewed by MySimulator Editorial Review

Last updated: 11 July 2026

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.