Aho-Corasick — Missing Output Links Drop 40% of Matches

Running KMP once per pattern scales linearly with pattern count. For 10,000 signatures on a 1 Gbps traffic stream, that's physically impossible at line rate. Aho-Corasick solves this by building a single deterministic automaton from all patterns upfront, then running the text through it exactly once — regardless of whether you have 10 patterns or 100,000.

Published in 1975 by Alfred Aho and Margaret Corasick at Bell Labs, the algorithm generalizes KMP's failure function to a trie. The failure links in Aho-Corasick are KMP failure function values applied across a shared prefix tree. If you understand why KMP doesn't restart from position zero on a mismatch, Aho-Corasick failure links will feel immediately familiar — the mechanics are identical, just extended to a tree instead of a linear string.

The trade-off is upfront preprocessing cost and a hard constraint: exact strings only. No wildcards, no quantifiers, no character classes. That limitation is precisely why it's fast — and precisely why it's the right tool when you need raw throughput on known, fixed signatures. When you need regex semantics at scale, you reach for Hyperscan. When you need to match a fixed dictionary of strings against a stream, you reach for Aho-Corasick.

Building the Trie

The first step is inserting all patterns into a trie — a prefix tree where each node represents a character on the path from root to some suffix. Nodes that complete a full pattern are marked as output nodes, storing the pattern ID (or the pattern string itself, depending on what you need to report).

The key property of the trie is prefix sharing. If two patterns share a common prefix, they share the corresponding nodes in the tree. Patterns 'http' and 'https' share five nodes — you only pay for the single divergent node at the 's'. A collection of 10,000 URL patterns with common prefixes like '/api/v1/', '/api/v2/' might compress to 2,000 trie nodes. A collection of 10,000 random hex strings compresses to almost nothing — nearly every character is a new branch.

The implementation below uses a list of dictionaries for the goto table. Each dictionary maps a character to the next node index. This is readable and correct for moderate-sized pattern sets with ASCII input. It breaks down with large alphabets (UTF-8 codepoints as characters rather than bytes) or very large node counts — at that scale the per-dict overhead in Python becomes a memory and cache-pressure problem. The correct fix in that scenario is pyahocorasick, which uses a C-backed double-array trie where each transition is a direct array index.

# io.thecodeforge.algo.aho_corasick_trie
from collections import deque


class AhoCorasick:
    """Aho-Corasick automaton for multi-pattern exact string matching.

    Build once with add_pattern() + build(), then call search() repeatedly.
    The automaton is immutable after build() — adding patterns after build
    requires a full rebuild.
    """

    def __init__(self):
        # goto[node][char] = next_node_id
        # Node 0 is the root. All failure links eventually reach 0.
        self.goto: list[dict[str, int]] = [{}]
        self.fail: list[int] = [0]
        # output[node] = list of pattern IDs that end at this node
        # After build(), also includes IDs inherited from failure link targets
        self.output: list[list[int]] = [[]]

    def add_pattern(self, pattern: str, pid: int) -> None:
        """Insert a pattern into the trie. Call before build()."""
        node = 0
        for ch in pattern:
            if ch not in self.goto[node]:
                # Allocate a new node
                self.goto.append({})
                self.fail.append(0)
                self.output.append([])
                self.goto[node][ch] = len(self.goto) - 1
            node = self.goto[node][ch]
        self.output[node].append(pid)


# --- Usage example ---
ac = AhoCorasick()
patterns = ['he', 'she', 'his', 'hers']
for i, p in enumerate(patterns):
    ac.add_pattern(p, i)

print(f'Trie nodes: {len(ac.goto)}')  # 11
# 'he', 'she' share no prefix with 'his', 'hers'
# 'his' and 'hers' share 'h' — one node
# Total unique prefixes across all four patterns: 11 nodes including root

Building Failure Links

Failure links are what separate Aho-Corasick from a trie with a linear scan per pattern. For each trie node v — reached by the path of characters representing some string S — the failure link points to the node representing the longest proper suffix of S that is also a valid prefix of some pattern in the set. If no such suffix exists, the failure link points to the root.

This is KMP's failure function, applied to every node in the trie simultaneously. When the search is at node v and the next character has no goto edge, following fail[v] gives you the best valid position to continue from — no characters rescanned, no match opportunity lost.

Failure links are built with BFS from the root, level by level. The ordering is non-negotiable: 1. Root's direct children all get fail = root (the root is its own failure destination) 2. For each node v at depth d, and each character c where v has a child: that child's failure link is goto(fail[v], c). This requires fail[v] to already be computed — which is why BFS level-ordering works and DFS does not. 3. The goto shortcut step: for characters not present in v's children, set goto[v][c] = goto[fail[v]][c]. This precomputes the 'where would failure take me?' step for every character, so search never needs to traverse a chain of failure links — one goto lookup is always sufficient.

The output merge happens here too, in the same BFS pass: self.output[child] += self.output[self.fail[child]]. This is covered in depth in the Output Links section, but it belongs in the build step — not in the search loop.

# io.thecodeforge.algo.aho_corasick_fail
# This method is added to the AhoCorasick class defined in aho_corasick_trie.py

    def build(self) -> None:
        """Build failure links and goto shortcuts using BFS.

        Must be called once after all patterns are added via add_pattern().
        After this call, the automaton is ready for search().
        Adding new patterns after build() requires a full rebuild.
        """
        q: deque[int] = deque()

        # Root's direct children: failure link = root (node 0)
        # Also compute goto shortcuts for root: any character not in root's
        # children loops back to root (same as KMP resetting to start)
        all_chars = set(ch for node in self.goto for ch in node)
        for ch in all_chars:
            if ch not in self.goto[0]:
                self.goto[0][ch] = 0  # Shortcut: unknown char at root -> stay at root

        for ch, child in list(self.goto[0].items()):
            if child != 0:  # Skip the shortcuts we just added
                self.fail[child] = 0
                q.append(child)

        while q:
            node = q.popleft()
            for ch, child in list(self.goto[node].items()):
                # Compute failure link for child:
                # Follow fail[node] until we find a node with a goto for ch
                # (or reach root). With root shortcuts, this is always O(1).
                f = self.fail[node]
                self.fail[child] = self.goto[f].get(ch, 0)

                # Guard against self-referential failure links
                # (can occur at root level without the shortcut above)
                if self.fail[child] == child:
                    self.fail[child] = 0

                # CRITICAL: merge output from failure link target
                # Without this line, patterns that are suffixes of other patterns
                # are silently dropped from results
                self.output[child] = self.output[child] + self.output[self.fail[child]]

                # Compute goto shortcuts for child:
                # For every character in the alphabet that child has no edge for,
                # precompute where failure would take us. This makes search O(1) per char.
                for c in all_chars:
                    if c not in self.goto[child]:
                        self.goto[child][c] = self.goto[self.fail[child]].get(c, 0)

                q.append(child)

Searching the Text

With failure links and goto shortcuts built, searching is a single linear pass through the text. For each character you follow a goto edge — which is O(1) because shortcuts were precomputed during build — land on the next node, and check its output list. The output list at each node already contains matches inherited from failure link targets, because the build step merged them. There is no chain to follow during search, no backtracking, no lookahead.

The search loop is simple enough to fit in a few lines. That simplicity is the result of doing all the hard work during build — the automaton encodes every mismatch-recovery decision as a precomputed edge, so the search just follows edges and collects outputs.

# io.thecodeforge.algo.aho_corasick_search
# This method is added to the AhoCorasick class

    def search(self, text: str) -> list[tuple[int, int]]:
        """Search text for all patterns. Returns (end_pos, pattern_id) pairs.

        end_pos is the index of the last character of the match.
        start_pos = end_pos - len(patterns[pattern_id]) + 1

        Requires build() to have been called first.
        Time complexity: O(n + k) where n = len(text), k = match count.
        """
        node = 0
        results: list[tuple[int, int]] = []
        for i, ch in enumerate(text):
            # With goto shortcuts, this is always a single dict lookup — O(1)
            # No failure link chain traversal needed during search
            node = self.goto[node].get(ch, 0)
            # output[node] already includes matches from failure link targets
            # — the build step merged them. No additional chain traversal here.
            for pid in self.output[node]:
                results.append((i, pid))
        return results


# --- Full example ---
ac = AhoCorasick()
patterns = ['he', 'she', 'his', 'hers']
for i, p in enumerate(patterns):
    ac.add_pattern(p, i)
ac.build()

matches = ac.search('ahishers')
for end, pid in matches:
    p = patterns[pid]
    print(f"'{p}' ends at index {end} (starts at {end - len(p) + 1})")

Complexity Analysis

Let n = text length, m = sum of all pattern lengths, k = total number of matches found.

Trie construction: O(m) — insert each character of each pattern once Failure link construction: O(m × |Σ|) with goto shortcut precomputation, where |Σ| is the alphabet size. For ASCII (|Σ| = 128) this is O(128m), which is O(m) with a constant factor. For full Unicode codepoints (|Σ| ≈ 140,000) this factor becomes significant — byte-level tries (|Σ| = 256) are the standard production choice for Unicode text. Search: O(n + k) — each character examined once, each match reported once Total: O(n + m + k)

This is provably optimal — you must read all input and report all matches. The critical observation is that pattern count does not appear in the search complexity. Searching with 10,000 patterns takes the same time as searching with 1, once the automaton is built. That is the entire value proposition of the algorithm.

The alphabet size factor in failure link construction is worth understanding before deployment. A byte-level trie (|Σ| = 256) has a constant factor roughly 10x larger than an ASCII lowercase trie (|Σ| = 26). For most production pattern sets this is absorbed — the build runs once and the search runs millions of times. But for very large pattern sets (millions of patterns) with byte-level alphabets, the build step can take tens of seconds. Profile it before assuming it's negligible.

Output Links — The Bug That Silently Drops Matches

Output links deserve their own section because they are the single most common source of production bugs in Aho-Corasick implementations, and because the failure mode is the worst kind: silent, correct-looking, and only detectable by knowing what should have been found.

The problem arises with overlapping patterns. Consider patterns 'she' and 'he'. In the trie, 'she' is represented by the path root → s → h → e. The node at the end of this path has fail pointing to the node representing 'he' (root → h → e), because 'he' is the longest suffix of 'she' that is also a pattern prefix. When the search reaches the 'she' terminal node, it should report both 'she' and 'he' — 'she' because that pattern ends here, and 'he' because the text at this position also ends a valid match for 'he'.

Without output merging, only 'she' is reported. The failure link is structurally correct — it points to the right node. But the output list at the 'she' terminal node only contains 'she'. The output at the 'he' node was never propagated.

The fix is one line in the BFS build loop: self.output[child] += self.output[self.fail[child]]. This propagates the output list from the failure link target into the current node at build time, so the search loop never needs to traverse failure links to collect outputs — it just reads the output list directly.

This is not a fringe case. Any pattern set that contains a pattern which is a suffix of another pattern exhibits this relationship. In URL pattern sets, '/api' is a suffix of '/internal/api'. In signature databases, short attack signatures are frequently substrings of longer ones. In content moderation, short slur variants are often substrings of longer ones. The overlap is the norm, not the exception.

# io.thecodeforge.algo.output_links_demo
# Side-by-side demonstration: broken vs correct output merging
# Both versions build failure links correctly — only output handling differs

from collections import deque


def build_broken(ac) -> None:
    """BROKEN: failure links correct, output merging missing.
    The automaton navigates correctly but silently drops suffix-pattern matches.
    """
    q: deque[int] = deque()
    for ch, child in ac.goto[0].items():
        ac.fail[child] = 0
        q.append(child)
    while q:
        node = q.popleft()
        for ch, child in ac.goto[node].items():
            f = ac.fail[node]
            while f != 0 and ch not in ac.goto[f]:
                f = ac.fail[f]
            ac.fail[child] = ac.goto[f].get(ch, 0)
            if ac.fail[child] == child:
                ac.fail[child] = 0
            # BUG: the following line is missing
            # ac.output[child] += ac.output[ac.fail[child]]
            q.append(child)


def build_correct(ac) -> None:
    """CORRECT: failure links and output merging both present."""
    q: deque[int] = deque()
    for ch, child in ac.goto[0].items():
        ac.fail[child] = 0
        q.append(child)
    while q:
        node = q.popleft()
        for ch, child in ac.goto[node].items():
            f = ac.fail[node]
            while f != 0 and ch not in ac.goto[f]:
                f = ac.fail[f]
            ac.fail[child] = ac.goto[f].get(ch, 0)
            if ac.fail[child] == child:
                ac.fail[child] = 0
            # CORRECT: propagate outputs from failure link target
            ac.output[child] = ac.output[child] + ac.output[ac.fail[child]]
            q.append(child)


# Test: patterns ['she', 'he'], text 'she'
# Expected matches: both 'she' (ends at index 2) and 'he' (ends at index 2)
# Broken result:  [(2, 'she')]          — 'he' silently dropped
# Correct result: [(2, 'she'), (2, 'he')] — both reported