Aho-Corasick: Search a Whole Dictionary of Patterns in One Pass

Searching for many patterns in one pass

Given one pattern and one text, a single-pattern search like KMP scans the text once. Given many patterns — say, a virus scanner checking a file against thousands of known signatures, or a text editor's multi-word highlighter — naively running a single-pattern search once per pattern costs O(n*k) for k patterns against text length n. Aho-Corasick, published by Alfred Aho and Margaret Corasick in 1975, finds every occurrence of every pattern from a whole dictionary in a single O(n) pass over the text, independent of how many patterns there are (beyond the fixed cost of building the automaton once).

Step one: build a trie

Insert every pattern into a standard trie (prefix tree): each edge is labelled with one character, and any node reached along a path from the root spells out the prefix formed by those characters. Nodes marking the end of a complete pattern are flagged as output nodes. So far this is nothing more than a shared-prefix data structure letting several patterns reuse the same nodes for any prefix they have in common.

Step two: failure links, the whole trick

A plain trie can only walk forward from the root, so if you are three characters deep matching one pattern and the fourth character does not match any of its children, the naive approach restarts the whole match from the root, throwing away the fact that the three characters you just read might themselves be a useful prefix of some other pattern. Aho-Corasick precomputes, for every node, a failure link: the node reached by following the longest proper suffix of that node's string that also happens to be a prefix somewhere else in the trie. On a mismatch, instead of restarting at the root, the automaton simply follows the failure link and continues matching from there — no character of input is ever re-read.

failure(node) = the trie node reached by the longest strict suffix of
                node's path-string that is also some prefix in the trie
                (root if no such suffix exists)

scan(text):
  node = root
  for ch in text:
    while node has no child for ch and node !== root:
      node = failure(node)              // follow failure link, don't re-read ch
    if node has child for ch: node = child
    output every pattern ending at node, and at every node reachable
      by following output links from node (patterns that are suffixes of it)

Failure links are computed once, in a single breadth-first sweep over the trie after all patterns are inserted, each node's failure link built from its parent's failure link (very similar in spirit to how KMP's single-pattern failure function is built, generalised from a chain to a tree). Because a character is consumed from the text at most once per successful transition and failure links only ever move to a strictly shorter string, the amortised cost of the whole scan is O(n) regardless of how many patterns are loaded into the automaton.

Output links: catching patterns that are suffixes of other matches

There is one more subtlety: if "he" and "she" are both patterns, arriving at the node for "she" should also report a match for "he", since it ends there too as a suffix. Each node additionally carries an output link to the nearest ancestor (via failure links) that is itself a pattern's endpoint, so reporting a match at any node also walks its chain of output links to report every shorter pattern ending at that same position — without this, the automaton would silently miss legitimate matches whenever one dictionary entry happens to be a suffix of the current match.

Where it actually gets used

Aho-Corasick is the classic algorithm behind the original Unix fgrep, and remains standard in antivirus and intrusion-detection engines scanning traffic or files against thousands of known signatures simultaneously, in bioinformatics tools searching a genome for many short motifs at once, and in any text-processing pipeline that needs to tag or redact a large fixed vocabulary (banned words, entity names, keyword sets) in one linear pass rather than one pass per term.

Frequently asked questions

Try it live

Everything above runs in your browser — open Aho-Corasick and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.