Aho-Corasick multi-pattern matching

What this chapter covers

The single-pattern algorithms found one needle in a haystack. Aho-Corasick finds thousands of needles in one pass. Given a whole dictionary of patterns — virus signatures, banned words, network-intrusion rules, a set of keywords — it locates every occurrence of every pattern in a single linear scan of the text, regardless of how many patterns there are or how long they are. The obvious alternative, searching for each pattern separately, re-reads the text once per pattern; Aho-Corasick reads it once, period. It achieves this by generalizing KMP's failure function from a single pattern to a trie of all patterns: arrange the patterns into a prefix tree, add failure links that say where to fall back when a character doesn't extend the current match, and feed the text through the resulting automaton. This chapter builds it, watches the classic ushers example find she, he, and hers in one sweep, and measures the payoff against per-pattern search: 260 times fewer character examinations.

A bit of history

Alfred Aho and Margaret Corasick published the algorithm in 1975 at Bell Labs, and its origin is delightfully concrete: it was built for a bibliographic-search library, to scan documents for many index terms at once. Aho would go on to co-author the "Dragon Book" on compilers and to co-create AWK (the "A" is his), but Aho-Corasick remains one of his most-deployed results — it runs inside fgrep, the classic Unix tool for fixed-string search, which is exactly the "find any of these strings" problem. The algorithm is a direct generalization of Knuth-Morris-Pratt, published just two years earlier: KMP's failure function tells one pattern where to resume after a mismatch, and Aho-Corasick's failure links do the same for a whole tree of patterns at once. The lineage is explicit — Aho-Corasick is what you get when you ask "what if KMP had a trie instead of a single string?" — and it made multi-pattern matching as cheap as single-pattern, which is why it became the standard tool for signature scanning.

The intuition

Build the algorithm in three layers. First, a trie: insert every pattern into a prefix tree, so he, she, his, and hers share their common prefixes as shared paths, and each pattern's last character marks a node as "a pattern ends here." Following characters down from the root is how you match — as long as the text keeps extending a path in the trie, you're inside a potential match.

Second, failure links, the KMP idea lifted to the tree. When the next text character doesn't continue the current trie path, you don't want to give up and restart from the root — you want to fall back to the longest proper suffix of what you've matched that is also a prefix of some pattern, and resume there. Each node's failure link points to exactly that node. They're computed by breadth-first traversal, shallow nodes first, because a node's failure target is always shallower and must be finished before you can compute the node's own — the same ordering dependency as KMP's table, now on a tree.

Third, output links. A single position in the text can end several patterns at once: arriving at the node for hers should also report he, because he is a suffix... no — hers contains he as a prefix, but the subtle case is she, which ends at a node whose failure link leads to he, so reaching she must also report he. Aho-Corasick handles this by merging each node's output set along its failure link, so a node reports its own pattern plus every pattern that is a suffix of the string it represents. Now feed the text through in one pass: at each character, follow a goto edge if it exists or failure links until one does, and emit the current node's outputs. The text pointer never moves backward — one linear sweep finds everything.

Complexity: how it scales

Building the automaton is $O(\sum \text{pattern lengths})$ — one trie node per distinct pattern character, plus a breadth-first pass for the failure links. Searching is $O(n + z)$ where $n$ is the text length and $z$ the number of matches reported: every text character is processed once (the failure-link fallbacks are amortized $O(1)$ per character, the same argument as KMP), plus constant work per match emitted. Crucially, the search cost is independent of the number of patterns — a thousand patterns cost the same single pass as one. That's the whole point, and the face-off measures it directly: character examinations to find $k$ patterns, Aho-Corasick's one pass versus scanning the text once per pattern:

The one-scan-per-pattern line climbs steadily: each new pattern means another full scan of the text, so its cost grows linearly with the number of patterns. Aho-Corasick's line is essentially flat — it processes the text once no matter how many patterns are in the automaton, so adding patterns only grows the (cheap) build, not the scan. At 500 patterns, Aho-Corasick examined about 10,000 characters against the per-pattern approach's 2.6 million — 260 times fewer, and the gap widens with every pattern added. This is the same "one pass beats many passes" story as Rabin-Karp's multi-pattern trick, but Aho-Corasick does it for patterns of any lengths and with a clean linear guarantee, which is why it, not Rabin-Karp, is the production tool for large dictionaries.

What it's good at, what it isn't

Aho-Corasick is the definitive tool for matching many fixed patterns at once. Its uses are exactly the "find any of these strings" problems: antivirus engines scanning files for thousands of malware signatures, network intrusion-detection systems (Snort, Suricata) matching packet streams against rule sets, spam and profanity filters checking against word lists, fgrep's multi-string search, and bioinformatics tools finding a set of motifs in DNA. Because its search cost is independent of the pattern count and it makes a single streaming pass with no backup, it's ideal for high-throughput, real-time scanning where the pattern dictionary is large and fixed. It also composes: the automaton, once built, can scan unlimited text, so you build once and stream forever.

Where it's the wrong tool is a single pattern (KMP or Boyer-Moore is simpler and Boyer-Moore is faster), or a frequently changing pattern set — the automaton must be rebuilt when patterns change, though the build is cheap relative to scanning lots of text. Its memory grows with the total size of the pattern dictionary (one node per distinct pattern-prefix character), which for enormous dictionaries can be significant, and the classic implementation stores a goto map per node; production versions use compact representations (double-array tries, bit-sliced automata) to shrink it. And for approximate or regex-style matching it doesn't apply directly — it's exact fixed-string matching. For that niche, though — many exact patterns, one text, linear time — nothing beats it.

The data, or the inputs

The face-off fixes a 5000-character random text and searches for a growing number of patterns, counting character examinations for Aho-Corasick's single pass versus scanning the text once per pattern — isolating the pattern-count independence. Correctness is checked on hundreds of random dictionaries and texts: Aho-Corasick's matches must exactly equal the result of searching for each pattern separately with Python's str.find. The animation runs the textbook example — the dictionary {he, she, his, hers} scanning the text ushers — drawing the trie and lighting up the current automaton state as each character is fed, firing matches (including the failure-link-reported he inside she) as they complete.

Build it, one function at a time

The trie — insert each pattern, sharing common prefixes:

class AhoCorasick:
    """A trie of patterns augmented with failure and output links — the Aho-Corasick automaton."""

    def __init__(self):
        self.goto = [{}]                          # goto[node][char] -> child node; node 0 is the root
        self.fail = [0]                           # failure link per node (filled in by build)
        self.out = [set()]                        # patterns ending at this node
        self.parent = [(-1, "")]                  # (parent node, edge char) — for drawing the trie

    def add(self, word):
        """Insert one pattern, creating trie nodes for any new characters along its path."""
        node = 0
        for ch in word:
            if ch not in self.goto[node]:
                self.goto.append({})
                self.fail.append(0)
                self.out.append(set())
                self.parent.append((node, ch))
                self.goto[node][ch] = len(self.goto) - 1
            node = self.goto[node][ch]
        self.out[node].add(word)                  # this node marks the end of `word`

The failure and output links — KMP's idea, built breadth-first over the tree:

def build(self):
    """Compute failure links by breadth-first traversal (shallower nodes first, so a node's
    failure target is already finished when we need it — the same order dependency as KMP's
    table). A node's failure link is the deepest OTHER node whose string is a proper suffix of
    this node's string. Output sets are merged along failure links, so reaching a node reports
    not just its own pattern but every pattern that is a suffix of it (that's how 'hers' also
    reports 'he')."""
    q = deque()
    for ch, nxt in self.goto[0].items():
        self.fail[nxt] = 0                     # depth-1 nodes fail to the root
        q.append(nxt)
    while q:
        u = q.popleft()
        for ch, v in self.goto[u].items():
            q.append(v)
            f = self.fail[u]                   # follow u's failure chain to find where ch continues
            while f and ch not in self.goto[f]:
                f = self.fail[f]
            self.fail[v] = self.goto[f].get(ch, 0) if self.goto[f].get(ch, 0) != v else 0
            self.out[v] |= self.out[self.fail[v]]   # inherit suffix patterns

And the single-pass search over the text:

def search(self, text):
    """Scan the text once. Follow goto edges when the next character extends the current match;
    on a dead end, follow failure links (never rewinding the text) until the character fits or
    we're back at the root. At each position, the current node's output set names every pattern
    ending here. Returns (start_index, pattern) for every occurrence. O(n + matches)."""
    node = 0
    results = []
    for i, ch in enumerate(text):
        while node and ch not in self.goto[node]:
            node = self.fail[node]             # fall back, like KMP, without moving in the text
        node = self.goto[node].get(ch, 0)
        for w in self.out[node]:
            results.append((i - len(w) + 1, w))
    return sorted(results)

Watch it work

Here's the automaton for {he, she, his, hers} scanning the text ushers. The diamond-marked (teal) nodes are where a pattern ends; orange is the automaton's current state. Feed the characters one at a time: u has no edge from the root, so we stay put; s steps to the s node, h to sh, e to she — and arriving at she fires two matches at once, she and he, because the output link merged he into she's outputs. Then r has no edge from she, so the automaton follows a failure link — falling back to the he node, which does have an r edge — and continues to her; the final s reaches hers and fires that match. One left-to-right pass, the text pointer never rewinding, and all three occurrences found:

The complete code

The from-scratch tab is the full Aho-Corasick automaton — trie, failure links, output merge, and search; the library tab is the one-scan-per-pattern approach it's checked and raced against, with the pyahocorasick call you'd use in production noted. Flip between them.

"""Aho-Corasick — find ALL occurrences of MANY patterns in one pass over the text. Rabin-Karp
could search many equal-length patterns; Aho-Corasick searches a whole dictionary of patterns of
any lengths, in a single linear scan, and it's the right tool when the pattern set is large: virus
signatures, network-intrusion rules, spam word lists, keyword filters.

It's KMP generalized from one pattern to many. First, arrange all the patterns into a TRIE (a
prefix tree) so shared prefixes are shared paths. Then add FAILURE LINKS exactly like KMP's
failure function, but on the trie: from each node, a failure link points to the node representing
the longest proper suffix of the current matched string that is also a prefix of some pattern —
where to fall back to when the next character doesn't extend the current match. Feed the text
through the resulting automaton one character at a time, following goto edges and failure links,
and OUTPUT links report every pattern that ends at the current position. One pass, O(n + total
pattern length + number of matches).
"""
from collections import deque


# region: trie
class AhoCorasick:
    """A trie of patterns augmented with failure and output links — the Aho-Corasick automaton."""

    def __init__(self):
        self.goto = [{}]                          # goto[node][char] -> child node; node 0 is the root
        self.fail = [0]                           # failure link per node (filled in by build)
        self.out = [set()]                        # patterns ending at this node
        self.parent = [(-1, "")]                  # (parent node, edge char) — for drawing the trie

    def add(self, word):
        """Insert one pattern, creating trie nodes for any new characters along its path."""
        node = 0
        for ch in word:
            if ch not in self.goto[node]:
                self.goto.append({})
                self.fail.append(0)
                self.out.append(set())
                self.parent.append((node, ch))
                self.goto[node][ch] = len(self.goto) - 1
            node = self.goto[node][ch]
        self.out[node].add(word)                  # this node marks the end of `word`
    # endregion

    # region: build
    def build(self):
        """Compute failure links by breadth-first traversal (shallower nodes first, so a node's
        failure target is already finished when we need it — the same order dependency as KMP's
        table). A node's failure link is the deepest OTHER node whose string is a proper suffix of
        this node's string. Output sets are merged along failure links, so reaching a node reports
        not just its own pattern but every pattern that is a suffix of it (that's how 'hers' also
        reports 'he')."""
        q = deque()
        for ch, nxt in self.goto[0].items():
            self.fail[nxt] = 0                     # depth-1 nodes fail to the root
            q.append(nxt)
        while q:
            u = q.popleft()
            for ch, v in self.goto[u].items():
                q.append(v)
                f = self.fail[u]                   # follow u's failure chain to find where ch continues
                while f and ch not in self.goto[f]:
                    f = self.fail[f]
                self.fail[v] = self.goto[f].get(ch, 0) if self.goto[f].get(ch, 0) != v else 0
                self.out[v] |= self.out[self.fail[v]]   # inherit suffix patterns
    # endregion

    # region: search
    def search(self, text):
        """Scan the text once. Follow goto edges when the next character extends the current match;
        on a dead end, follow failure links (never rewinding the text) until the character fits or
        we're back at the root. At each position, the current node's output set names every pattern
        ending here. Returns (start_index, pattern) for every occurrence. O(n + matches)."""
        node = 0
        results = []
        for i, ch in enumerate(text):
            while node and ch not in self.goto[node]:
                node = self.fail[node]             # fall back, like KMP, without moving in the text
            node = self.goto[node].get(ch, 0)
            for w in self.out[node]:
                results.append((i - len(w) + 1, w))
        return sorted(results)
    # endregion

"""The library counterpart and the contrast. For production multi-pattern matching you'd use a
maintained Aho-Corasick library (`pyahocorasick`, a C extension) or a regex engine's alternation:

    import ahocorasick
    A = ahocorasick.Automaton()
    for i, w in enumerate(patterns):
        A.add_word(w, (i, w))
    A.make_automaton()
    for end, (i, w) in A.iter(text):
        ...

The instructive contrast is the obvious alternative: search for each pattern SEPARATELY, one pass
over the text per pattern. `search_each` below does exactly that with str.find — the correctness
reference and the k-passes cost Aho-Corasick's single pass is timed against.
"""


# region: per_pattern
def search_each(text, patterns):
    """Find every pattern by searching for each one independently — one full scan of the text per
    pattern (k patterns → k scans). Returns the same (start, pattern) list Aho-Corasick produces,
    so it's both the correctness reference and the 'naive multi-pattern' contrast."""
    results = []
    for w in patterns:
        if not w:
            continue
        i = text.find(w)
        while i != -1:
            results.append((i, w))
            i = text.find(w, i + 1)               # +1 → overlapping occurrences
    return sorted(results)
# endregion

Scratch vs library

Aho-Corasick is the capstone of this tier because it unifies its threads. It's KMP's failure function (chapter one of the tier) generalized to a trie (the trees-tier prefix tree), solving the multi-pattern version of the problem Rabin-Karp's multi-search hinted at, with the clean linear guarantee the field spent the 1970s establishing. The recurring lesson of the strings tier is on full display: matching gets its speed from precomputing structure before the scan — KMP's table, Rabin-Karp's rolling hash, Boyer-Moore's skip table, the suffix array's index, and now Aho-Corasick's automaton are all the same move, pay upfront to make the scan cheap. And the one-pass-beats-many-passes result mirrors Rabin-Karp's multi-pattern trick and the suffix array's amortized queries: when you'll do a lot of matching, compile the work into a structure once. In production you'd use pyahocorasick (a C extension) for the throughput; building the automaton yourself is what makes the failure-link-and-output-merge machinery — the part that's easy to get subtly wrong — something you understand rather than trust.

Where you'll actually meet it

Aho-Corasick runs in the security and text infrastructure you rely on daily. Antivirus and anti-malware engines scan files against dictionaries of thousands of byte signatures with it. Network intrusion-detection and prevention systems — Snort, Suricata, and the deep-packet-inspection engines in firewalls — match packet payloads against large rule sets in real time using Aho-Corasick (and its compact variants). Content filters, profanity and spam detectors, and data-loss-prevention systems match against keyword lists. Search tools (fgrep, grep -F with multiple patterns, ripgrep's multi-literal path) use it or close relatives. Bioinformatics uses it to find sets of DNA/protein motifs, and computational linguistics for dictionary tokenization. Anywhere a stream must be matched against many fixed strings at once, at speed, Aho-Corasick is almost certainly the engine.

Takeaways

Aho-Corasick compiles a whole dictionary of patterns into a single automaton — a trie of the patterns plus KMP-style failure links and merged output links — and finds every occurrence of every pattern in one linear pass over the text, with a search cost independent of the number of patterns (260× fewer examinations than per-pattern search at 500 patterns). It's the multi-pattern generalization of KMP: failure links are KMP's failure function on a tree, output merging ensures every pattern ending at a position is reported, and the scan is amortized linear for the same reason KMP's is.

That completes the strings tier — single-pattern search three ways (KMP, Rabin-Karp, Boyer-Moore), text indexing (suffix arrays), and multi-pattern matching (Aho-Corasick) — all united by the theme of precomputing structure to make the scan cheap. The book now turns from specific data structures and problems to the paradigms that generate algorithms: the next tier is about the reusable strategies — divide and conquer, greedy, dynamic programming, backtracking, two pointers — that underlie much of what you've already built, making explicit the patterns that have been recurring implicitly throughout.