Aho-Corasick Algorithm, in depth: the complete automaton, the failure tree, per-pattern counts and dynamic programming over states

States, failure links and the complete transition table

Insert every pattern into a trie. Each trie node is a state, and it stands for the string spelled on the path from the root. Call that string the state's label. The failure link of a state points to the state whose label is the longest proper suffix of its own label that is also in the trie. The root's label is the empty string, so a failure link always exists.

The construction is a breadth-first search. A state's failure target is strictly shorter than the state itself, so BFS order guarantees the target is finished first. The version below also fills in the full transition function delta. If a state has no trie edge on symbol x, then delta[s][x] equals delta[fail[s]][x], which BFS has already computed. After construction, the scanner never follows a failure link at run time.

from collections import deque

def build(patterns, alphabet):
    goto, fail, term = [dict()], [0], [[]]       # term[s]: ids of patterns ending at s
    for i, pat in enumerate(patterns):
        s = 0
        for ch in pat:
            if ch not in goto[s]:
                goto.append({}); fail.append(0); term.append([])
                goto[s][ch] = len(goto) - 1
            s = goto[s][ch]
        term[s].append(i)                         # a list, so duplicate patterns survive
    idx = {ch: k for k, ch in enumerate(alphabet)}
    delta = [[0] * len(alphabet) for _ in goto]
    order, q = [], deque()
    for ch, k in idx.items():                     # depth-1 states fail to the root
        if ch in goto[0]:
            t = goto[0][ch]; delta[0][k] = t; q.append(t)
    while q:
        s = q.popleft(); order.append(s)          # order = BFS order, root excluded
        for ch, k in idx.items():
            t = goto[s].get(ch)
            if t is None:
                delta[s][k] = delta[fail[s]][k]   # borrow the answer from the fail state
            else:
                fail[t] = delta[fail[s]][k]
                delta[s][k] = t
                q.append(t)
    return delta, fail, term, order, idx

Construction costs O(S x A) time and memory, where S is the number of states (at most the total pattern length plus one) and A is the alphabet size. That table is the price of a branch-free scan. When A is 256 bytes and S is in the millions, the table no longer fits in cache, and the section on operations covers what to do about it.

The failure tree

Every non-root state has exactly one failure link, and that link points to a strictly shorter label. So the links form a tree rooted at the root, called the failure tree (or suffix-link tree). Walking up from a state visits every suffix of its label that is also a trie node, longest first.

That gives the key lemma. After the scanner reads text position i, it sits in the state whose label is the longest suffix of the text so far that is a trie node. Pattern P ends at position i if and only if P's state is an ancestor of the current state in the failure tree, or the state itself. The occurrences of P are therefore the visits to states in the subtree under P's state. The figure shows the trie and failure links for the patterns a, ab and bab.

Counting every pattern without listing matches

Suppose you need, for each pattern, the number of times it occurs, and nothing else. Reporting every occurrence and tallying costs O(n + z), where z is the number of matches. z can be huge: with the patterns a, aa, up to a repeated k times, a text of n copies of a produces about n x k matches. The failure tree removes z entirely. Count how often the scanner visits each state, then push the counts up the tree. A pattern's count is the total for its subtree.

def count_each(patterns, text, alphabet):
    delta, fail, term, order, idx = build(patterns, alphabet)
    hits = [0] * len(delta)
    s = 0
    for ch in text:                    # one lookup per symbol, no failure walks
        s = delta[s][idx[ch]]
        hits[s] += 1
    for s in reversed(order):          # children before parents in the failure tree
        hits[fail[s]] += hits[s]
    out = [0] * len(patterns)
    for s, ids in enumerate(term):
        for i in ids:
            out[i] = hits[s]
    return out

Total cost is O(n + S x A) no matter how many matches there are. Reverse BFS order is a valid bottom-up order because each failure target is shallower than its source. The same pass answers related questions. Which patterns occur at least once? Those with a nonzero subtree sum. Which state was the scanner in at each position? That is the array you already walked, and you can keep it for later position queries.

Worked example: a, ab and bab over babab

Take the patterns a, ab and bab over the alphabet {a, b} and the text babab. BFS numbers the states as in the figure: 1 = a, 3 = b, 2 = ab, 4 = ba, 5 = bab. Construction produces fail(ab) = b, fail(ba) = a and fail(bab) = ab. The scan reads b, a, b, a, b and visits states 3, 4, 5, 4, 5. On the fourth symbol, state 5 (bab) has no trie edge on a, so delta[5][a] is borrowed from state 2 (ab), which borrows from state 3 (b), which has an edge to 4 (ba). The scanner never sees that chain. It only reads the precomputed entry.

Visit counts before accumulation: state 3 once, state 4 twice, state 5 twice. The reverse BFS order is 5, 4, 2, 3, 1. State 5 adds 2 to state 2, state 4 adds 2 to state 1, and state 2 then adds its 2 to state 3. The final subtree counts are a = 2, ab = 2 and bab = 2. Check by hand: a occurs at offsets 1 and 3, ab at 1 and 3, and bab at 0 and 2. A second check: for the patterns a, aa and aaa over aaaa, the code returns 4, 3 and 2.

Dynamic programming over automaton states

The automaton remembers exactly the part of the input that can still matter for future matches. That makes it a natural state space for dynamic programming over strings you have not seen yet. The classic question: how many strings of length L over the alphabet contain none of the patterns?

Mark a state as bad if any pattern ends there. That means the state is accepting, or any ancestor in the failure tree is. Then count walks of length L from the root that never enter a bad state.

def count_avoiding(patterns, alphabet, L, mod=10**9 + 7):
    delta, fail, term, order, idx = build(patterns, alphabet)
    bad = [bool(t) for t in term]
    for s in order:                    # BFS order: a state's fail target is done first
        bad[s] = bad[s] or bad[fail[s]]
    ways = [0] * len(delta); ways[0] = 1
    for _ in range(L):
        nxt = [0] * len(delta)
        for s, w in enumerate(ways):
            if w and not bad[s]:
                for t in delta[s]:
                    if not bad[t]:
                        nxt[t] = (nxt[t] + w) % mod
        ways = nxt
    return sum(ways) % mod

Run time is O(L x S x A). A hand check: over {a, b}, the strings of length 5 that avoid ab are exactly b...ba...a, one for each split point, which gives 6. Avoiding aa gives 13, the Fibonacci number you would expect. The same skeleton handles a family of problems:

• Must contain at least one pattern: all strings minus the avoiding count.
• Maximum score: give each pattern a weight, give each state the sum of weights along its failure-tree path, and replace (+, x) with (max, +) to find the best-scoring string of length L.
• Huge L: the step is a fixed S x S matrix, so repeated squaring costs O(S^3 log L). This works for L near 10^18 when S is a few hundred.
• Constrained generation: intersect the automaton with another one (a digit-DP bound, or a grammar) and run the same walk on product states. Decoders use this idea to ban token sequences.

Operational guidance

The full table is fast but large. With byte input (A = 256) and 4-byte state ids, each state costs 1 KB. A million states needs about a gigabyte, and most lookups then miss cache. The standard responses, in rough order of payoff:

• Byte classes. Bytes that appear in no pattern all behave the same, and so do bytes that always appear together. Map each byte to a class id first. Real dictionaries often need only a few dozen classes, and the table shrinks by the same factor.
• Dense near the root, sparse below. The states the scanner visits most are shallow. Keep full rows for the top few levels and sparse edge lists plus failure links deeper down, where visits are rarer.
• Build once, share read-only. Construction is single-threaded and allocation-heavy. The finished table is immutable, so threads and processes can share it, for example through a memory-mapped file.
• Track size. Record S, A and table bytes for each dictionary version, and alert on jumps. A pattern list that doubles overnight is usually a data bug, not a scaling problem.

For counting jobs, process the text in chunks and keep the scanner state between chunks. Visit counts can be added across chunks before the single accumulation pass, so a distributed job can ship S counters per worker instead of match lists.

Failure modes

• Accepting flags not propagated. With the patterns bc and abcd, the state abc is not itself accepting, but its failure path passes through bc. If you only check the current state's own flag, the text abc reports nothing. In the DP, a string such as abca gets counted as clean. Propagate along failure links in BFS order, or follow output links when reporting.
• Wrong accumulation order. Pushing visit counts up in insertion order instead of reverse BFS order adds a child into its parent after the parent has already passed its total on. Counts come out too low, and only for nested patterns, which tiny tests often lack.
• Duplicate and empty patterns. A single terminal id per state silently drops duplicates. An empty pattern makes the root accepting: it matches at every position, and in the DP it makes every string bad. Decide explicitly and reject it at load time.
• Alphabet mismatch. idx[ch] raises on a symbol outside the alphabet. Production code needs a catch-all class that sends the scanner back to the root, and case folding or Unicode normalisation applied the same way to patterns and text.
• Testing only on small examples. Compare against a brute-force oracle on random patterns and texts over a two-letter alphabet. Small alphabets force overlaps and nested suffixes, which is where these bugs live. The code on this page passed hundreds of such trials for both counting and the DP.

Trade-offs and alternatives

Use Aho-Corasick when the patterns are fixed and many texts stream past. For a single pattern, a simpler matcher has less setup and smaller state; see String Matching, in depth. When the text is fixed and patterns arrive later as queries, invert the roles and index the text with a suffix structure instead. When the patterns are regular expressions rather than literals, Aho-Corasick becomes a prefilter at best, and the real matcher is an NFA or DFA engine (Regex Engines, in depth). The trie at the core is the same structure described in Trie in Depth, and the failure links are what turn a prefix tree into a matcher.

Within Aho-Corasick, the main choice is full table or failure links. The full table costs S x A memory and gives exactly one lookup per symbol. Failure links cost memory proportional to the trie edges and give amortised O(1) per symbol, with branchy, data-dependent loops. Choose the table when S x A fits in cache-friendly memory after byte-class compression, and failure links when it does not.

What to do next

1. Implement build and count_each, reproduce the babab trace above, and draw the failure tree for your own three patterns.
2. Write the brute-force oracle (count occurrences with repeated str.startswith) and run 1,000 random trials over {a, b}.
3. Solve one avoid-or-contain counting problem with count_avoiding, then convert it to matrix powering for L = 10^18.
4. Measure S, the class count and table bytes on your real dictionary before you pick between a full table and failure links.
5. Read the companion article for match semantics (leftmost-first versus leftmost-longest) before you put the scanner behind a user-facing search box.