Aho-Corasick

Imagine you have a list of a thousand words — names, keywords, forbidden phrases — and a long text to scan. The obvious approach is to run a search for each word one at a time. If the text has n characters and the dictionary has k words, the naïve total is $O(n \cdot k)$ comparisons: fifty thousand passes through a fifty-page document.

In 1975, Alfred Aho and Margaret Corasick at Bell Labs published a single algorithm that does all the searching in $O(n + m + z)$ time — where m is the total length of all patterns and z is the number of matches found. It doesn't matter how many patterns there are; you pay for each one only once, at build time.

The trick is to compile the dictionary into a finite automaton: a machine that reads the text one character at a time, keeps track of the longest dictionary prefix it has seen so far, and never backtracks. Each pattern match triggers a report; then the machine marches forward.

That guarantee — one character in, one state transition, guaranteed progress — is what makes Aho-Corasick feel almost miraculous. It was described as solved the moment the paper appeared: the algorithm is optimal in the worst case, and improvements since then are constants, not complexity classes.

Type any text and a comma-separated list of keywords. Click Search and the automaton highlights every match it finds — potentially overlapping — in a single left-to-right pass.

<p class="hint">{{hint}}</p>
<div class="inputs">
  <label>{{label_text}}<textarea id="text" rows="3">{{default_text}}</textarea></label>
  <label>{{label_keywords}}<input id="keywords" type="text" value="{{default_kw}}"/></label>
</div>
<div id="output" class="output"></div>
<div class="stats" id="stats"></div>
<div class="btns">
  <button id="search" type="button">{{btn_search}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.inputs { display: flex; flex-direction: column; gap: .5rem; margin-bottom: .7rem; }
label { font-size: .85rem; font-weight: 600; display: flex; flex-direction: column; gap: .25rem; }
textarea, input[type=text] { font: 14px ui-monospace, monospace; padding: .4rem .5rem;
  border: 1px solid #adb1b8; border-radius: 6px; width: 100%; resize: vertical; }
.output { font: 15px ui-monospace, monospace; white-space: pre-wrap; word-break: break-all;
  background: #f4f6f8; border: 1px solid #cdd9e3; border-radius: 8px; padding: .6rem .8rem;
  min-height: 2.4em; line-height: 1.7; margin-bottom: .5rem; }
.output span.hi { border-radius: 3px; padding: 0 1px; }
.stats { font-size: .88rem; color: #444; min-height: 1.2em; margin-bottom: .6rem; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
  border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.legend { display: flex; gap: .6rem; flex-wrap: wrap; margin-top: .5rem; font-size: .8rem; }
.legend-item { display: flex; align-items: center; gap: .25rem; }
.legend-dot { width: 12px; height: 12px; border-radius: 3px; display: inline-block; }

// Code not found

Notice that the algorithm reports matches at overlapping positions without restarting. Compare this to running each keyword separately: for a large dictionary the savings are dramatic. The failure links (shown in the console output) are the key — when a partial match fails, the automaton jumps to the longest suffix that is still a valid prefix of some pattern, instead of rewinding the text pointer.

The algorithm has three phases, each with its own cost:

• Build the trie — $O(m)$. Insert every pattern character by character. The trie has at most m nodes (total pattern length).
• Compute failure links — $O(m)$. A BFS over the trie fills in each node's failure link: the longest proper suffix of the current string that is also a prefix of some pattern. This is the secret that eliminates backtracking.
• Scan the text — $O(n + z)$. Read each of the n characters once. At each position follow the automaton transition (or the failure link if there is no direct transition). Every state reached that corresponds to a match end emits a report; there are exactly z such events.

Total: $O(n + m + z)$. This is optimal: you must read the text once (n), you must encode the patterns (m), and you must report the matches (z). No algorithm can do better in the worst case.

Compare this to running the naïve approach or even a single-pattern algorithm like KMP for each word separately: $O(n \cdot k)$ versus $O(n + m + z)$. For large dictionaries the difference is the gap between reading once and reading ten thousand times.

The goto function (trie edges), failure function (suffix links), and output function (which states emit which patterns) together form a deterministic finite automaton that recognizes the union of all patterns. Once built, it is just a state-machine lookup per character — the fastest possible model of sequential computation.

Whenever the task is "scan a stream for any of thousands of known strings," Aho-Corasick is the standard answer:

• Antivirus and malware detection: a scanner must check every file against a database of millions of byte signatures. Aho-Corasick (or its variants) makes this feasible in real time.
• Network intrusion detection (Snort, Suricata): packets are matched against thousands of attack signatures per second; linear-time multi-pattern search is non-negotiable.
• Spam and content filtering: finding hundreds of forbidden phrases in an email without re-scanning the body for each one.
• Bioinformatics: searching a genome for many primer sequences or known gene motifs simultaneously — the genome is long and the motif library is large.
• Search engines and plagiarism detection: locating known phrases or boilerplate text in large document collections.
• Compiler lexers: tokenizing source code by recognizing keywords, operators, and literals in a single pass over the source.

The algorithm also appears under different names inside database systems, log parsers, and firmware. Wherever you see the phrase "dictionary-based search" or "signature matching," there is a good chance Aho-Corasick is running underneath.

Aho-Corasick is one of those rare algorithms where the problem is genuinely solved: the 1975 paper gave the asymptotically optimal answer, and fifty years of follow-up work has produced only constant-factor improvements.

The deeper lesson is about automata. Compiling a set of patterns into a single finite state machine, then running the machine over the input without ever moving backwards, is a template that reappears in lexers, protocol parsers, hardware pattern-matching circuits, and network deep-packet inspection. The failure-link construction is a specific instance of a much broader idea: when a tentative match fails, don't discard all the work you did — reuse the longest prefix that can still lead somewhere useful.

If you want to see the same principle at work in single-pattern search, look at KMP pattern matching. If you want to understand why some search problems resist this kind of speedup and end up NP-complete, explore SAT and P vs NP. Aho-Corasick is a reminder that not every hard-looking problem stays hard once you find the right structure.