Aho-Corasick, in depth: one pass over the text for thousands of patterns

The problem: many patterns, one pass

Let the patterns be P₁..P_k with total length m, and the text T of length n. The naive approach tests every pattern at every position: O(n · m) in the worst case. Running Knuth-Morris-Pratt once per pattern gives O(k · n + m), which is still a full pass over the text per pattern. Hashing approaches such as Rabin-Karp handle many patterns of one length well but degrade when lengths vary widely.

Aho-Corasick generalises KMP's idea. KMP precomputes, for each prefix of one pattern, where to resume after a mismatch without moving backwards in the text. Aho-Corasick does the same over a trie of all the patterns: every state is a prefix of some pattern, and every mismatch jumps to the longest proper suffix of the text read so far that is also a prefix of some pattern. The text pointer never moves backwards, so the text can arrive as a stream.

Trie, failure links and output links

The automaton has three components.

1. Goto function (the trie). Insert each pattern character by character. A state is identified with the string spelled from the root to it. In the figure, state 4 is sh and state 9 is hers. Shared prefixes share states, so he and hers share states 1 and 2.
2. Failure links. For state s spelling string u, fail(s) is the state for the longest proper suffix of u that is also a state in the trie. The failure link for she is he, because he is the longest proper suffix of she that is in the trie. For his it is s. When the next text character has no goto edge, follow failure links until one does or you reach the root.
3. Output (dictionary) links. A state may end a pattern itself, and suffixes of its string may end other patterns. Reaching she means he has also just ended. The output link of s points to the nearest state on its failure chain that ends a pattern, so reporting all matches visits only states that produce output.

Building the automaton

Failure links must be computed in breadth-first order. A state's failure target is always shallower than the state, so its own failure link is already known when it is processed. Depth-1 states fail to the root. For a child t of state s reached by character ch, walk s's failure chain until some state f has an edge on ch, then fail(t) = goto(f, ch), or the root if none does.

from collections import deque

def build(patterns):
    goto = [{}]          # state -> {char: next_state}
    fail = [0]           # failure link
    out = [[]]           # ids of patterns that end exactly at this state
    dict_link = [-1]     # nearest state on the failure chain with output, or -1
    for pid, pat in enumerate(patterns):
        s = 0
        for ch in pat:
            if ch not in goto[s]:
                goto.append({}); fail.append(0); out.append([]); dict_link.append(-1)
                goto[s][ch] = len(goto) - 1
            s = goto[s][ch]
        out[s].append(pid)
    q = deque(goto[0].values())          # depth-1 states fail to the root
    while q:
        s = q.popleft()
        for ch, t in goto[s].items():
            f = fail[s]
            while f and ch not in goto[f]:
                f = fail[f]
            fail[t] = goto[f].get(ch, 0)
            ft = fail[t]
            dict_link[t] = ft if out[ft] else dict_link[ft]
            q.append(t)
    return goto, fail, out, dict_link

def search(text, patterns, auto):
    goto, fail, out, dict_link = auto
    s = 0
    for i, ch in enumerate(text):
        while s and ch not in goto[s]:
            s = fail[s]
        s = goto[s].get(ch, 0)
        t = s if out[s] else dict_link[s]
        while t > 0:                     # walk only states that emit output
            for pid in out[t]:
                yield i - len(patterns[pid]) + 1, patterns[pid]
            t = dict_link[t]

This code was checked against a brute-force matcher on 2,000 random pattern sets over a two-letter alphabet, where overlaps and nested patterns are most frequent. Each match is reported as (start offset, pattern). Duplicate patterns are fine: both ids land in the same out list.

Worked example: four patterns over ushers

Take patterns he, she, his, hers and the text ushers. Building produces ten states:

Scanning character by character:

1. u: the root has no u edge, so stay at 0.
2. s: go to 3.
3. h: go to 4 (sh).
4. e: go to 5 (she). Emit she at offset 1, then follow the output link to 2 and emit he at offset 2.
5. r: state 5 has no r edge. Fail to 2 (he), which has one, so go to 8 (her). The text pointer did not move back. The automaton simply reinterpreted the last two characters as the start of a different pattern.
6. s: go to 9. Emit hers at offset 2.

The output, copied from running the code, is [(1, 'she'), (2, 'he'), (2, 'hers')]. Matches come out ordered by end position, not start. If callers need start order, sort them or use a leftmost match mode, covered below.

Why the scan is linear

Why is the scan linear? Track the depth of the current state. Each text character increases depth by at most one, since a goto edge goes exactly one level down. Every failure step strictly decreases depth. Depth never goes below zero, so the total number of failure steps over the whole text is at most n. Each output-link step emits a match, so output walking costs O(z) for z matches. The scan is therefore O(n + z) transitions.

The same potential argument bounds construction. Along the trie path of a single pattern, the failure depth rises by at most one per character and falls with every chain step, so computing failure links costs O(m) chain steps in total. Each step is a child lookup, which costs O(1) with a dense table or hash map, or O(log σ) with sorted edges over an alphabet of size σ.

Without output links, reporting walks the whole failure chain at every position: O(n · L) for longest pattern L, even when nothing matches.

Memory layouts decide real speed

Asymptotics decide little in practice. The cost of each transition dominates, and it depends on how states are stored.

A full DFA precomputes delta(s, c) for every state and byte by resolving the failure walk at build time: delta(s, c) = goto(s, c) if it exists, else delta(fail(s), c). Filling it in BFS order makes the search loop branch-free. The cost is memory. Ten thousand patterns averaging 20 bytes can yield up to about 200,000 states, roughly 200 MB as a dense 32-bit table, which no longer fits in cache. Then a compact NFA with failure links can beat the DFA. Byte classes help both: if the patterns only use 40 distinct bytes, every other byte behaves identically and can share one column.

Production libraries make these choices explicit. The Rust aho-corasick crate used by ripgrep lets callers choose between NFA and DFA representations. For small pattern sets it can also use a SIMD prefilter instead of the automaton. Benchmark on your own patterns and text: the right layout depends on state count and match density, not only on the theory.

Match semantics: overlapping, leftmost-first, leftmost-longest

The automaton above reports all overlapping matches. Many applications want something else:

• Standard, overlapping: every occurrence of every pattern. Right for counting, indexing, and intrusion signatures where any hit matters.
• Leftmost-first: scan for the earliest-starting match, and among matches at that start, prefer the pattern listed first, the way a regex alternation a|ab prefers a. Then resume after it, so matches do not overlap.
• Leftmost-longest: earliest start, then the longest pattern at that start. This is what a dictionary tokenizer or a redaction pass usually means: replacing New York City beats replacing New York inside it.

Leftmost semantics cannot be had by filtering the overlapping output after the fact without buffering. A shorter match ends first, so you cannot know whether a longer match starting at the same offset is coming. Libraries implement them by changing how the automaton is built and when the search stops. The aho-corasick crate calls these MatchKind::Standard, LeftmostFirst and LeftmostLongest. Pick the semantics explicitly. Silently getting Standard when you meant leftmost-longest is a classic source of double-redacted or half-replaced text.

Streaming, bytes and case folding

Because the only search state is one integer, Aho-Corasick streams naturally. Process the input in chunks, carry the state across chunk boundaries, and keep a running offset. A pattern that straddles two chunks is found when its last byte arrives, with no overlap buffer. To stream with the search function above, keep s outside the chunk loop and add a running base offset to each reported position.

Bytes versus characters. Matching UTF-8 bytes is safe for valid UTF-8 patterns and text: UTF-8 is self-synchronising, so an encoded pattern can only match at a character boundary. Byte automata also keep the alphabet at 256. Case-insensitive matching for ASCII is easy: lowercase patterns at build time and map each text byte through a 256-entry fold table. Full Unicode case folding is harder because folding can change length (German ß folds to ss), and composed and decomposed forms of accented letters differ byte-for-byte. Normalise both sides to the same form (for example NFC plus case folding) before building and scanning, and remember that reported offsets then refer to the normalised text, not the original.

Failure modes

• Output explosion. Patterns a, aa, aaa, ... up to length L over a run of a's report L matches per position. The algorithm stays linear in n + z, but z itself is O(n · L). Cap matches per position, or switch to leftmost semantics, when patterns come from users.
• Memory blow-up from a dense DFA. Loading a large signature list into a 256-wide table can consume gigabytes. Estimate states times columns times 4 bytes before choosing the layout.
• Recursive or unordered failure computation. Computing failure links depth-first reads failure links that are not computed yet. It must be BFS.
• Forgotten output links. Omitting them silently drops nested matches. The scan for ushers would miss he. A brute-force cross-check on random small alphabets catches this in seconds.
• Empty patterns. An empty pattern matches at every offset and makes the root an output state. Reject it at build time unless you really want n + 1 matches.
• Mismatched normalisation. Patterns folded one way and text another produce misses that look random. Run both through one function.

Trade-offs and alternatives

Choose Aho-Corasick when you have many fixed strings and want one pass with guaranteed linear time. For a single pattern, Boyer-Moore is usually faster in practice because it skips text, which Aho-Corasick never does. If patterns need wildcards, classes or repetition, you need a regular expression engine. Many such engines detect literal alternations and use Aho-Corasick internally. If the pattern set is huge and changes constantly, a plain trie walked from each start position avoids the BFS rebuild at the cost of O(n · L) scanning. Signature scanners such as ClamAV and network intrusion detection systems use Aho-Corasick variants because worst-case input is adversarial and the linear-time guarantee matters more than average speed.

What to do next

1. Implement build and search from this page and run them on he, she, his, hers over ushers. Confirm the three matches and the order.
2. Write a brute-force checker and fuzz on a two-letter alphabet with random pattern sets until thousands of cases pass.
3. Delete the output links, rerun the fuzzer and watch it catch the missed nested matches, so you know the test works.
4. Fold failure links into a dense DFA, then measure state count, memory and throughput against the NFA on your real pattern set.
5. Decide the match semantics your product needs (overlapping, leftmost-first or leftmost-longest) and write a test that fails under the wrong one.
6. Fix one normalisation function for patterns and text, and document what reported offsets refer to.