Searching for one word is a small drama.

Searching for a dictionary is a scheduling problem.

Suppose the dictionary is:

he
she
his
hers

and the stream says:

ushers

At the e in ushers, both she and he have ended. At the r, hers is still alive. A naive matcher can try every pattern at every position and discover these facts by repetition.

Aho-Corasick stores the repetition.

The trie stores what has matched so far. Failure links store what remains true after the next character disappoints you.

A Trie Is Not Enough

A trie is the obvious first move. Put every keyword into one prefix tree:

h -> e
  -> i -> s
s -> h -> e
          -> r -> s

Now a shared prefix is only stored once. Good.

But streaming search has a harder problem. If you are in the state for sh and the next character is e, you have found she. If the next character had been i, you should not restart the entire scan. The suffix h is still a prefix of another keyword. It deserves to stay alive.

A failure link answers:

if this prefix cannot be extended by the current character,
what is the longest suffix of this prefix that is also a trie prefix?

That sounds like a mouthful because it is doing careful bookkeeping. It is the multi-pattern cousin of KMP’s border table. KMP remembers fallback positions inside one pattern. Aho-Corasick remembers fallback positions inside a whole dictionary trie.

Aho and Corasick’s 1975 paper describes the algorithm as constructing a finite state pattern-matching machine from the keywords and then applying the text as input to that machine.1 The important promise is that the text pointer does not move backward. The machine changes state; the stream keeps going.

The Output Function Is a Separate Thing

One small detail is easy to miss.

Reaching a node does not necessarily mean there is only one output.

In a dictionary such as:

he
she

one ending position can report several patterns, because he is a suffix of she. In a dictionary such as GAT and GATA, the shorter pattern is instead a prefix of the longer one, so standard all-matches search reports both facts at adjacent endpoints. The automaton’s output function has to include:

patterns that end at this trie node
patterns inherited through failure links

This is why practical libraries expose choices about match semantics. The Rust aho-corasick crate, for example, documents multiple-pattern search through a finite state machine and exposes different match kinds for use cases that want standard overlapping matches, leftmost-first matches, or leftmost-longest matches.2

The mathematical automaton can report everything.

The product API still has to decide what “everything” means for replacement, highlighting, tokenization, or moderation.

The Lab

The lab below builds the automaton directly. It shows four things:

trie edges:       solid green character transitions
failure links:   red suffix fallbacks
stream trace:    one pass over generated text
work ledger:     naive comparisons versus automaton work

It also computes a dense DFA table for comparison. The sparse failure-link machine has fewer stored transitions but may take extra fallback steps. A filled DFA precomputes those fallbacks into every state/character transition, so search can be one table lookup per byte, but the table is larger.

The Rust implementation notes make exactly this kind of engineering tradeoff: users can choose NFAs or a DFA, and the design discusses contiguous representations, dense transitions, memory, and speed.3 Hyperscan, a production multiple-regex matcher, goes much further with hybrid automata and CPU-oriented decomposition; the point here is the small exact core, not the full industrial stack.4

Exact substring matching only. The 145,384-check audit compares sparse AC, dense DFA, and naive all-pattern scans across generated streams plus 1,875 exhaustive short strings.

The failure link is not an error handler. It is a cached theorem:

this shorter prefix is still compatible with the suffix just seen

When the sparse machine cannot follow a character edge, it falls through failure links until it reaches a state that can consume that character, or returns to the root. That sounds like it could be expensive, but the stream-position does not move backward. The state can only fall after it previously climbed through matched characters. The usual amortized story is the same kind of story that makes KMP linear.

The original paper separates recognition cost from output cost: before printing matches, the machine makes one forward transition per input character and fewer than twice as many total state transitions as input characters.1 That caveat matters, because a dictionary can be constructed so many patterns end at nearly every position. Reporting facts is still work.

A dense DFA makes a different bargain. It asks, ahead of time:

from every state, for every alphabet character, where would the sparse machine land?

Then search is simple:

state = table[state][char]
emit output[state]

That can be fast and predictable, especially when the alphabet is small and the machine fits cache. It can also be too large. The table size is roughly:

states * alphabet

while the sparse trie stores only explicit character edges plus failure links. The right representation depends on pattern count, alphabet, cache behavior, match semantics, and build-time budget.

This is why “use Aho-Corasick” is not a single implementation decision. It is a family of automata layouts.

When Outputs Stack

The DNA dictionary in the lab includes both:

GAT
GATA

If the stream contains GATA, a standard all-matches automaton reports both. That is the mathematically clean output.

But consider a replacement API:

replace ["GAT", "GATA"] with ...

Should it replace GAT first? Prefer GATA because it is longer? Prefer the pattern listed earlier? Report both and let the caller decide?

Those are not automaton questions. They are policy questions on top of the automaton.

This distinction matters in real text systems:

syntax highlighters
tokenizers
moderation filters
intrusion signatures
DNA motif scanners
log alerting rules
bulk literal replacement

In each case, the automaton can find candidate facts. The application decides which candidates are allowed to overlap, suppress, rewrite, or escalate.

Why This Still Feels Modern

Aho-Corasick is old enough to look like textbook furniture. It should not feel old.

It has the same shape as many modern systems:

compile a large set of rules into a reusable state machine
stream data through it once
emit all local events without rescanning
choose a memory layout for the hardware you actually have

Hyperscan’s NSDI paper describes a far more elaborate version of that world: large-scale regular-expression matching decomposed into string and automata components, with modern CPU optimizations layered on top.4 The original exact-keyword algorithm is not the whole story, but it is one of the cleanest ancestors of the story.

The moral I keep is small:

a failed partial match is not wasted work

If you can name what remains true after a failure, you can store that fact as a link. The next character does not have to retry the past. It can inherit it.

Reproducibility Notes

The executable artifact is assets/js/aho-corasick-lab.js.

The implementation builds:

trie next edges
failure links by breadth-first traversal
output lists inherited through failure links
a sparse scanner with explicit failure steps
a dense transition table for memory comparison
a naive all-pattern scanner for audit

The self-test runs 135 generated cases and 1,875 exhaustive short-string cases:

3 dictionaries * 5 seeds * 3 stream lengths * 3 overlap settings
2 binary adversarial suites through length 7
1 DNA suite through length 5

It also pins three hand-checkable overlaps: she, ushers, and GATA.

For every generated case, it verifies that Aho-Corasick and the naive scan report the same (start, end, pattern) triples. The exhaustive cases also compare a dense-DFA scanner against the same naive oracle. The audit checks that failure links point to the longest proper suffix state, output lists are exactly the patterns that suffix the current state word, the dense DFA table agrees with the sparse failure-walk transition function, and streams stay under the two-transitions-per-character recognition bound.

The block below is the static-site audit runner target:

node - <<'NODE'
const lab = require("./assets/js/aho-corasick-lab.js");
const EXPECTED_CHECKS = 145384;
const EXPECTED_EXHAUSTIVE = { cases: 1875, totalMatches: 4550 };
const EXPECTED_KNOWN = { gata: 2, she: 2, ushers: 3 };
const EXPECTED_SUMMARY = {
  classic: "45:1699:1.542",
  dna: "45:1328:1.917",
  logs: "45:536:1.333"
};

function fixed3(value) {
  return Number(value).toFixed(3);
}

function sameJson(actual, expected) {
  return JSON.stringify(actual) === JSON.stringify(expected);
}

const audit = lab.audit();
const summary = {};
Object.keys(audit.summary).sort().forEach((key) => {
  const row = audit.summary[key];
  summary[key] = [
    row.cases,
    row.totalMatches,
    fixed3(row.maxSparseStepsPerChar)
  ].join(":");
});

if (
  !audit.ok ||
  audit.checked !== EXPECTED_CHECKS ||
  !sameJson(audit.exhaustive, EXPECTED_EXHAUSTIVE) ||
  !sameJson(audit.knownExamples, EXPECTED_KNOWN) ||
  !sameJson(summary, EXPECTED_SUMMARY)
) {
  throw new Error(JSON.stringify({
    checked: audit.checked,
    exhaustive: audit.exhaustive,
    knownExamples: audit.knownExamples,
    ok: audit.ok,
    summary
  }, null, 2));
}

console.log(`${audit.checked} Aho-Corasick checks passed`);
NODE

  1. Alfred V. Aho and Margaret J. Corasick, “Efficient string matching: an aid to bibliographic search”, Communications of the ACM, 1975. A PDF is mirrored at cr.yp.to. ↩ ↩2

  2. Andrew Gallant, aho-corasick crate documentation, docs.rs. ↩

  3. Andrew Gallant, aho-corasick design notes, especially the discussion of NFA and DFA representations. ↩

  4. Xiang Wang, Yang Hong, Harry Chang, KyoungSoo Park, Geoff Langdale, Jiayu Hu, and Heqing Zhu, “Hyperscan: A Fast Multi-pattern Regex Matcher for Modern CPUs”, NSDI 2019. Intel’s developer introduction is also useful: Introduction to Hyperscan. ↩ ↩2