StringsAlgorithmaka multi-pattern matching, trie with failure links, dictionary matching automaton

Aho–Corasick

Search a text for every word of a dictionary simultaneously by walking a trie augmented with KMP-style failure links.

▶ VisualizePattern: Breadth-First SearchPractice (2)
Progress

Overview

Aho–Corasick finds all occurrences of all k patterns in a text in O(n + total pattern length + number of matches). It generalises Knuth–Morris–Pratt (KMP) from one pattern to a dictionary: the patterns are stored in a Trie, and every trie node gets a failure link pointing to the longest proper suffix of its string that is also a prefix of some pattern — exactly what the LPS array does for a single string.

The result is a deterministic automaton. Reading the text one character at a time, the current node always represents the longest suffix of the text read so far that is a prefix of some pattern. Whenever that node (or any node reachable by failure links, via output links) marks the end of a pattern, a match is reported.

multiple patternstriefailure linksautomatonO(n + m + z)

Intuition

A mental model before the formal terms.

Lay out all the patterns as branching paths from a common root. Walking the text down these paths is easy until a character has no branch. Instead of returning to the root and re-reading, you jump to the deepest other path that ends with the same characters you have just read — the failure link. It is the same slide-without-forgetting idea as KMP, except the "pattern" is a whole tree.

Output links solve a subtlety: after reading "she" you are at the node for "she", but "he" also ends here. The failure chain from "she" passes through "he", so following it (or a precomputed shortcut to the nearest pattern node) reports every pattern that is a suffix of the current position.

How it works

  1. Insert every pattern into a trie; mark terminal nodes with the pattern index.
  2. Compute failure links in BFS order from the root. For the root's children, fail = root. For a node v reached from u by character c: follow u.fail, u.fail.fail, … until a node with a child on c exists (or the root); v.fail is that child (or the root).
  3. Set v.output = v.fail if v.fail is terminal, otherwise v.output = v.fail.output — a shortcut to the nearest terminal node on the failure chain.
  4. Scan the text: for each character c, follow failure links from the current node until a child on c exists, then move to it. Report the current node if terminal, then walk its output chain reporting every terminal node.
  5. Optionally precompute full goto transitions for every (node, character) so each text character costs exactly one table lookup.

Why it works

Invariant: after reading t[0..i], the current node is the longest suffix of t[0..i] that is a prefix of some pattern. Adding one character either extends that suffix (child exists) or must shorten it; the failure link gives the next-longest candidate, and the BFS construction guarantees every failure link is the longest such suffix, so no shorter valid state is skipped.

Every pattern occurrence ending at i is a suffix of t[0..i] and a prefix of itself, so it lies on the failure chain of the current node; the output links enumerate exactly those chain nodes that are terminal.

Amortised bound: depth of the current node increases by at most 1 per character and each failure step decreases it, so failure steps over the whole text are at most n. Construction is O(total length · σ) with full transitions or O(total length) amortised with lazy failure walking.

Recognition

How to tell a problem wants this.

  • Search a text for many words at once: spam filters, banned-word detection, "count how many dictionary words appear in the string".
  • The naive approach is "run KMP once per pattern", and k · n is too large.
  • DP over an automaton: "count strings of length L that avoid all forbidden substrings" — the AC automaton is the state space.
“minimum steps” → Breadth-First Search“prefix” → Trie

Interactive visualization

Play, step, change the input. ← → and space work too.

Showing the closely related Trie visualization.

●
1/43Empty trie: only the root. Each edge holds one character, and a node with the "end" badge terminates a stored word.
Matched prefixCurrent nodeNew nodeMatch / word end
PseudocodeLearn Trie →
1node = root
2for ch in word:
3  if ch not in node.children: (insert) create child / (search) return false
4  node = node.children[ch]
5insert: node.end = true
6search: return node.end
7startsWith: return true
Variables
words0
Complexity
access —
search O(L)
insert O(L)
delete O(L)
Speed

Pseudocode

1build trie of all patterns
2queue = children of root, their fail = root
3while queue: u = pop; for (c, v) in u.children:
4  f = u.fail; while f != root and c not in f.children: f = f.fail
5  v.fail = f.children[c] if c in f.children and f.children[c] != v else root
6  v.output = v.fail if v.fail terminal else v.fail.output; push v
7node = root; for i, c in text:
8  while node != root and c not in node.children: node = node.fail
9  node = node.children.get(c, root)
10  for w in node, node.output, node.output.output, …: report (i, w.pattern)

Implementations

1from collections import deque
2 
3 
4class AhoCorasick:
5    """A trie of all patterns plus "failure" links that point to the longest
6    proper suffix which is also a prefix of some pattern. One pass over the
7    text finds every occurrence of every pattern, in O(text + total + hits)."""
8 
91 · One node per trie position; fail is the suffix link, out the matches
10    def __init__(self) -> None:
11        self.next: list[dict[str, int]] = [{}]
12        self.fail: list[int] = [0]
13        self.out: list[list[int]] = [[]]  # ids of patterns ending here
14        self.out_link: list[int] = [-1]  # next node up the fail chain with output
15 
16    def _new_node(self) -> int:
17        self.next.append({})
18        self.fail.append(0)
19        self.out.append([])
20        self.out_link.append(-1)
21        return len(self.next) - 1
22 
232 · Insert every pattern into the trie, recording its id at the end
24    def add(self, pattern: str, ident: int) -> None:
25        cur = 0
26        for c in pattern:
27            nxt = self.next[cur].get(c)
28            if nxt is None:
29                nxt = self._new_node()
30                self.next[cur][c] = nxt
31            cur = nxt
32        self.out[cur].append(ident)
33 
343 · BFS builds failure links: a node's fail is its parent's fail + c
35    def build(self) -> None:
36        q = deque()
37        for child in self.next[0].values():
38            self.fail[child] = 0
39            q.append(child)
40        while q:
41            u = q.popleft()
42            f = self.fail[u]
43            # out_link skips straight to the next ancestor that actually matches
44            self.out_link[u] = f if self.out[f] else self.out_link[f]
45            for c, v in self.next[u].items():
46                f2 = self.fail[u]
47                while f2 != 0 and c not in self.next[f2]:
48                    f2 = self.fail[f2]
49                cand = self.next[f2].get(c)
50                self.fail[v] = cand if cand is not None and cand != v else 0
51                q.append(v)
52 
534 · Walk the text once; on a mismatch follow fail links, never backing up
54    def search(self, text: str) -> list[tuple[int, int]]:
55        hits: list[tuple[int, int]] = []  # (end index, pattern id)
56        cur = 0
57        for i, c in enumerate(text):
58            while cur != 0 and c not in self.next[cur]:
59                cur = self.fail[cur]
60            cur = self.next[cur].get(c, 0)
61 
625 · Report this node's patterns, then follow output links for the rest
63            node = cur
64            while node != -1:
65                for ident in self.out[node]:
66                    hits.append((i, ident))
67                if node == 0:
68                    break
69                node = self.out_link[node]
70        return hits
Walkthrough
  1. This version uses four *parallel lists* (next, fail, out, out_link) rather than a node class, which avoids one Python object per node and is measurably lighter for large automata.
  2. self.next[cur].get(c) returns None for a missing transition, and is None is the correct test — a node index of 0 is falsy and would break a truthiness check.
  3. self.next[cur].get(c, 0) in search supplies the root as the default target, which is the fall-back-to-root behaviour.
  4. for i, c in enumerate(text) iterates index and character together; Python strings iterate by code point, so no surrogate handling is needed.
  5. The out_link chain is walked with an explicit while because Python has no C-style for with three clauses.
Complexity (this implementation)
time O(sum of pattern lengths) to build, O(text length + number of matches) to search · space O(sum of pattern lengths) nodes
Language notes
  • Parallel lists beat a per-node class in CPython: each object otherwise costs a __dict__ (or __slots__ overhead) plus a reference, which adds up over hundreds of thousands of nodes.
  • dict.get(key) returning None versus dict.get(key, 0) is the difference between "is there a transition" and "where do I go" — both spellings appear here deliberately.
  • collections.deque is the right BFS queue; list.pop(0) would be O(n).
  • pyahocorasick is the established C extension if this is needed in production.
Common mistakes in this language
  • Testing if self.next[cur].get(c): instead of is None, which treats node index 0 as missing.
  • Using a list with pop(0) for the BFS queue.
  • Building failure links depth-first, so a parent's link is not final when its child is processed.
Language differences that matter here
  • The falsy-zero trap appears in three languages at once and in different disguises: || versus ?? in JS/TS, and truthiness versus is None in Python. Node index 0 is the root, so "missing" and "goes to 0" must stay distinguishable.
  • Node storage: C++ and JS/TS use an array of node records, while the Python version uses parallel lists to dodge per-object overhead — the same structure, a different memory trade.
  • Reference stability: only C++ has to worry that push_back invalidates a held Node&; JS/TS objects and Python list elements are separately allocated.
  • String iteration: Python and JS/TS for...of walk code points, while a charCodeAt or C++ char loop walks units and bytes — the automaton is correct either way, but the pattern and the text must agree.

Complexity

Best
O(n + L + z)
Average
O(n + L + z)
Worst
O(n + L + z)
Space
O(L · σ)

L = total pattern length, z = number of reported matches, σ = alphabet size (for full transition tables).

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Matching a dictionary of many words against one or many texts.
  • Counting or locating occurrences of each of k patterns in a single pass.
  • Automaton DP: counting strings that contain/avoid a set of substrings, or "minimum edits to remove all forbidden words".
Avoid it when
  • A single pattern — Knuth–Morris–Pratt (KMP) is simpler with the same bound.
  • Patterns change frequently — the automaton must be rebuilt; a Suffix Array of the text answers ad-hoc queries instead.
  • Huge alphabets with full transition tables — memory O(L·σ) explodes; use lazy failure walking or hash-map children.

Alternatives

Knuth–Morris–Pratt (KMP)Rabin–KarpSuffix ArrayTrie

Common mistakes

  • Computing failure links with DFS instead of BFS — a node's failure link depends on shallower nodes being finished.
  • Setting v.fail = v when the failure walk from the root lands back on v itself (happens for depth-1 nodes).
  • Reporting only the current node and forgetting output links, missing patterns that are suffixes of other patterns ("he" inside "she").
  • Reporting end indices but returning them as start indices; the start is end - len(pattern) + 1.

Interview patterns

  • Word Search II can be solved with a trie; Aho–Corasick is the follow-up for "find all dictionary words in a long text".
  • Stream checker: "has any word in the dictionary just been completed by the stream?"
  • Count occurrences of each keyword in a document.
  • Forbidden-substring DP with the automaton as state.
Interview questions on this
Mock interviews

Example problems

Word Search IIhardFind the Index of the First Occurrenceeasy