Back to String Processing Dsa

Aho-Corasick Failure Automaton

September 16, 2026 Wasil Zafar 6 min read

Failure links, output links, and output-sensitive multi-pattern search

Table of Contents

  1. From Trie to Automaton
  2. Failure and Output Links
  3. Search and Reporting
  4. Counting and Automaton DP

From Trie to Automaton

Insert every pattern into a trie. Each node is a state representing the string on its root path, each edge appends one symbol, and terminal nodes store pattern identifiers. Identifiers preserve duplicate patterns and caller metadata.

Trie edges handle successful extensions only. Aho–Corasick adds a failure link from each state to the deepest proper suffix of its represented string that is also a trie state. The root represents the empty string and fails to itself; its children fail to the root. On a missing edge, follow failures until a compatible edge appears or the root is reached.

After reading a text prefix, the current state represents its longest suffix that is also a prefix of some pattern. Sparse maps save memory for large alphabets; completed transition tables use more memory but make every state-symbol transition one lookup.

Trie states for {he, she, his, hers} hseihres roothsheoutput: hehishhersheoutput: shehersoutput: hers Terminal statestores pattern IDs

Build failure links in breadth-first order so every parent and shallower transition is ready before its children. Root children fail to the root. For edge $v\xrightarrow{c}u$, begin at $\operatorname{fail}(v)$, follow failures while no $c$ edge exists, and set $\operatorname{fail}(u)$ to the discovered destination or root.

Failure chains enumerate progressively shorter dictionary suffixes. If a failure ancestor is terminal, its pattern ends at the same text position. Thus reaching she must report both she and its terminal suffix he. Implementations may merge inherited outputs during BFS or store an output link to the nearest terminal failure ancestor; reporting time is charged to emitted matches.

Failure automaton
flowchart TD
    ROOT["root"]
    S["state s"]
    SH["state sh"]
    SHE["state she; output she"]
    H["state h"]
    HE["state he; output he"]
    REPORT["report she and he"]
    ROOT -->|s| S
    S -->|h| SH
    SH -->|e| SHE
    ROOT -->|h| H
    H -->|e| HE
    SH -. failure .-> H
    SHE -. failure/output .-> HE
    HE -. failure .-> ROOT
    SHE --> REPORT

Search and Reporting

For each text symbol, follow failure links until the current state has a matching edge or is the root, take the edge when present, and emit every pattern ID in the destination's output list. Search never resets after reporting, so overlapping matches and multiple patterns ending at one position are handled naturally.

With constant-time transitions, total pattern length $L$, text length $n$, and $z$ emitted matches, construction and search require $O(L+n+z)$ time under the standard automaton model. The $z$ term is unavoidable when the caller requests every match.

from collections import deque
from dataclasses import dataclass, field


@dataclass
class Node:
    children: dict[str, int] = field(default_factory=dict)
    failure: int = 0
    output: list[int] = field(default_factory=list)
    match_count: int = 0


class AhoCorasick:
    def __init__(self, patterns: list[str]) -> None:
        if any(pattern == "" for pattern in patterns):
            raise ValueError("empty patterns require a boundary-match policy")
        self.patterns = patterns[:]
        self.nodes = [Node()]
        for pattern_id, pattern in enumerate(patterns):
            self._insert(pattern, pattern_id)
        self._build()

    def _insert(self, pattern: str, pattern_id: int) -> None:
        state = 0
        for symbol in pattern:
            next_state = self.nodes[state].children.get(symbol)
            if next_state is None:
                next_state = len(self.nodes)
                self.nodes[state].children[symbol] = next_state
                self.nodes.append(Node())
            state = next_state
        self.nodes[state].output.append(pattern_id)

    def _build(self) -> None:
        queue: deque[int] = deque()
        for child in self.nodes[0].children.values():
            self.nodes[child].failure = 0
            self.nodes[child].match_count = len(self.nodes[child].output)
            queue.append(child)

        while queue:
            state = queue.popleft()
            for symbol, child in self.nodes[state].children.items():
                fallback = self.nodes[state].failure
                while fallback and symbol not in self.nodes[fallback].children:
                    fallback = self.nodes[fallback].failure
                failure = self.nodes[fallback].children.get(symbol, 0)
                self.nodes[child].failure = failure
                self.nodes[child].output.extend(self.nodes[failure].output)
                self.nodes[child].match_count = len(self.nodes[child].output)
                queue.append(child)

    def transition(self, state: int, symbol: str) -> int:
        while state and symbol not in self.nodes[state].children:
            state = self.nodes[state].failure
        return self.nodes[state].children.get(symbol, 0)

    def search(self, text: str) -> list[tuple[int, int, int, str]]:
        """Return (start, inclusive end, pattern ID, pattern)."""
        state = 0
        matches: list[tuple[int, int, int, str]] = []
        for end, symbol in enumerate(text):
            state = self.transition(state, symbol)
            for pattern_id in self.nodes[state].output:
                pattern = self.patterns[pattern_id]
                matches.append((end - len(pattern) + 1, end, pattern_id, pattern))
        return matches

    def count_all_occurrences(self, text: str) -> int:
        state = total = 0
        for symbol in text:
            state = self.transition(state, symbol)
            total += self.nodes[state].match_count
        return total


if __name__ == "__main__":
    automaton = AhoCorasick(["he", "she", "his", "hers"])
    assert automaton.search("ushers") == [
        (1, 3, 1, "she"),
        (2, 3, 0, "he"),
        (2, 5, 3, "hers"),
    ]
    assert automaton.count_all_occurrences("ushers") == 3

    overlapping = AhoCorasick(["a", "aa", "aaa"])
    assert len(overlapping.search("aaaa")) == 9
    assert overlapping.count_all_occurrences("aaaa") == 9

    duplicates = AhoCorasick(["aba", "aba"])
    assert duplicates.search("ababa") == [
        (0, 2, 0, "aba"), (0, 2, 1, "aba"),
        (2, 4, 0, "aba"), (2, 4, 1, "aba"),
    ]
    print(automaton.search("ushers"))

Counting and Automaton DP

To count all matches without listing them, store at each state the number of terminal patterns in its output/failure chain and add that value after each transition. To count occurrences per pattern, count visits to states during the scan, then propagate visit totals from deeper states to failure parents in reverse BFS order; a terminal node's propagated total is its pattern frequency.

The automaton is also a DP state graph. Mark states whose output chain contains a forbidden pattern, then let dp[length][state] count generated strings that remain in safe states. Transition on each alphabet symbol and discard forbidden destinations. This supports counting avoiding strings, lexicographically smallest valid strings, digit DP, shortest paths, and probability models. Large lengths can use matrix exponentiation over safe states.

For total pattern length $L$, text length $n$, and $z$ reported occurrences, Aho–Corasick runs in $O(L+n+z)$ time under constant-time automaton transitions; the $z$ term is required by the output itself. Counting modes replace explicit reporting with aggregated state counts and scan the text in $O(n)$ after construction.