What problem does Aho-Corasick solve?

It finds all occurrences of many patterns (a dictionary) inside a text in a single pass. Instead of running a separate search for each pattern, it combines them into one automaton and scans the text once, in O(text length + total pattern length + number of matches).

How is Aho-Corasick related to KMP?

It's the multi-pattern generalization of the Knuth-Morris-Pratt algorithm. KMP's prefix-function fallback for a single pattern becomes Aho-Corasick's failure links over a trie of many patterns. Both avoid re-scanning the text by remembering the longest reusable suffix.

Where is Aho-Corasick used?

Anywhere a stream is scanned against a fixed dictionary: intrusion-detection and antivirus signature matching, spam and profanity filters, DNA/protein motif search in bioinformatics, and keyword highlighting. Its linear scan makes it ideal for large texts and large pattern sets.

Algorithms · Strings

One Pass Catches Every Word.

Q: What is a failure link?

A failure link points from a trie node to the node representing the longest proper suffix of the current matched string that is also a prefix of some pattern. On a mismatch, the automaton follows failure links instead of restarting from the root, so no text character is ever re-read.

Scan a text for a whole dictionary of words at once. Running a separate search per word is slow; Aho-Corasick stitches the patterns into a single trie, adds failure links that say where to fall back on a mismatch, and walks the text one character at a time — never re-reading a character, firing every match as it goes. O(text + matches).

O(text + patterns + matches) · one pass · multi-pattern

the trie

All patterns share prefixes in one tree; a path spells a pattern prefix.

goto edge

The next character moves you down the trie — a normal transition.

failure link

On a mismatch, jump to the longest suffix that's still a pattern prefix.

output

A node fires every pattern that ends there — including via failure links.

aho.js — trie + failure links, scanned in one pass

Ready

Patterns he · she · his · hers built into a trie (green goto edges) with failure links (red, dashed). Press Step to scan the text ushers: each character either follows a goto edge deeper, or — when there's no edge — follows failure links back until one fits. Double-ringed nodes fire matches.

state

–

text pos

matches

How it works

The trie alone can only match patterns that start where you happen to be. The insight is the failure link: when the current character has no goto edge, the longest suffix of what you've matched so far might still begin another pattern — so you slide to that node instead of throwing away progress and restarting at the root. It's exactly KMP's fallback, generalized from one pattern to a tree of them.

Build the trie

Insert every pattern; shared prefixes share a path. Mark each pattern's final node with its output.

Wire failure links (BFS)

For each node, its failure link points to the node spelling the longest proper suffix that is also a trie prefix — computed level by level from the root.

Scan the text once

For each character: if a goto edge exists, take it; otherwise follow failure links until one does (or reach the root). Never move the text cursor backward.

✓

Report outputs

At each state, emit every pattern ending there. Because outputs chain along failure links, one position can fire several matches at once (e.g. she also ends he).

Scan

O(n + z)

Build

O(Σ|pattern|)

text length

# matches

The code

# goto[state][char], fail[state], output[state] already built def search(text): s = 0 for i, c in enumerate(text): while s != 0 and c not in goto[s]: s = fail[s] # fall back on mismatch s = goto[s].get(c, 0) # take the edge (or reset to root) for pat in output[s]: # fire every match ending here report(pat, end=i) # failure links, by BFS (output[] merges along the way) for node in bfs_order: f = fail[parent]; while f and c not in goto[f]: f = fail[f] fail[node] = goto[f].get(c, 0) output[node] += output[fail[node]]

The while loop looks quadratic but isn't: across the whole scan the state depth rises by at most one per character and each failure jump lowers it, so total work is linear in the text length. Merging output[fail[node]] into output[node] at build time is what lets a single state report nested matches like he inside she without walking the failure chain during the scan.

Quick check

1. On a character with no goto edge, why follow the failure link instead of restarting at the root?

2. Scanning ushers, reaching the node for she fires two matches. Why?

Right — he is a suffix of she, so the "she" node's output set (merged from its failure link) includes he. One position, two matches: she@1–3 and he@2–3.

FAQ

What problem does it solve?

Finding all occurrences of many patterns in a text in one linear pass, rather than searching for each pattern separately.

What is a failure link?

A pointer to the node spelling the longest proper suffix of the current match that is also a prefix of some pattern — where to fall back on a mismatch.

How does it relate to KMP?

It's the multi-pattern generalization of KMP: the prefix-function fallback becomes failure links over a trie of patterns.

Where is it used?

Intrusion detection, antivirus signatures, spam/profanity filters, and DNA motif search — anywhere a stream is matched against a fixed dictionary.

Keep going

Finished this one? 0 / 62 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

One Pass Catches Every Word.

How it works

Build the trie

Wire failure links (BFS)

Scan the text once

Report outputs

The code

Quick check

FAQ

Keep going

Explore the topic

More Algorithms

Explore more from Vibe Engines

How it works

Build the trie

Wire failure links (BFS)

Scan the text once

Report outputs

The code

Quick check

FAQ

Keep going

Knuth–Morris–Pratt →

Tries →

Rabin–Karp →

The DSA Roadmap →

Explore the topic

More Algorithms

Explore more from Vibe Engines

Get the next one in your inbox.