Aho-Corasick algorithm in short

Aho–Corasick — multi-pattern string matching in one pass

The problem. You have a set of patterns {he, she, his, hers} and a text ushers. You want every occurrence of every pattern — including overlapping ones — in a single left-to-right scan of the text. Aho–Corasick does this in O(text length + number of matches), no matter how many patterns you have.

Think of it as KMP generalized to many patterns at once. KMP builds a "fallback" table for one pattern; Aho–Corasick builds a fallback automaton for a whole dictionary.

The one-sentence idea

Glue all patterns into a trie, then add failure links so that whenever the next character doesn't extend the current match, you jump to the longest proper suffix that is still a valid prefix of some pattern — instead of starting over from scratch.

Step 1 — Build the trie (shared prefixes)

Each node = one prefix of some pattern. Shared prefixes share nodes. A node is an output node if its string is a complete pattern.

Patterns: he, she, his, hers

        (0) root
       /        \
     h(1)        s(3)
    /    \         \
  e(2)*   i(6)      h(4)
  |        \         \
  r(8)      s(7)*     e(5)*
  |
  s(9)*

  * = output node (a full pattern ends here)

Step 2 — Failure links (the heart of the algorithm) ⭐

The failure link of a node v points to the node representing the longest proper suffix of v's string that is also a node in the trie (i.e. a prefix of some pattern). Root → itself.

Intuition: "I matched the string v so far. If I now get a character that breaks the match, what's the longest tail of what I've read that could still be the start of a pattern?"

These are computed bottom-up by BFS (shallow nodes first), using a clean recurrence:

fail(child via char c) = go( fail(parent), c )

i.e. to find where a node falls back to, take the parent's fallback and try to follow c from there. Because BFS processes parents before children, fail(parent) is always ready.

Step 3 — The transition function go(v, c)

This turns the trie into a true automaton: every (state, character) pair has a defined next state, so reading the text never "gets stuck."

go(v, c):
    if v has a real trie edge for c:   return that child
    if v is root:                      return root        # stay put
    else:                              return go(fail(v), c)   # fall back and retry

Follow the failure link and retry until an edge exists or you hit the root. With BFS precomputation each transition is O(1) amortized.

Step 4 — Reporting all matches (and the output-link optimization)

The problem: one position can finish several patterns at once

When the scan lands on a node, more than one pattern may end right there. A node's own "I'm a complete pattern" flag only tells you about one of them — you'd silently miss the rest.

Example: you've just matched she (node 5). Look at its suffixes — she, he, e, "". Both she and he are patterns, and both end at this exact position. Checking only "is this node an output node?" reports she and drops he. That's the bug this step fixes.

The key fact: matches-ending-here are exactly the output nodes on the failure chain

Recall fail(v) = the longest proper suffix of v that's still a trie node. So following failure links from your current node walks through every suffix of what you've matched that exists in the trie:

she ──fail──▶ he ──fail──▶ root

A pattern ends at the current position iff it's a suffix of what you've matched — i.e. iff it's an output node somewhere on this chain. So the rule is simply:

Follow the failure chain up to the root, and report every output node you pass.

at "she":   she   (output ✅ → report "she")
             │ fail
             he    (output ✅ → report "he")
             │ fail
            root   (stop)

→ reports she and he. Done.

The optimization: output links skip the junk

The failure chain often contains nodes that aren't patterns. Walking past them to find the few that are is wasted work. The output link pre-wires each node straight to the next output node above it — forming a second, compressed chain over the same nodes that contains only output nodes:

failure chain:   she ─▶ (junk) ─▶ he ─▶ (junk) ─▶ root
output chain:    she ───────────▶ he ───────────▶ (end)    ← non-patterns spliced out

Now reporting only ever lands on real matches — no checking, no wasted steps. That's what makes search O(text + number of matches): every step of this traversal produces a match.

• node 5 (she) → output link → node 2 (he) ⇒ reaching she reports she and he

Two overlays, two jobs: failure links drive matching (every node, pattern or not); output links drive reporting (output nodes only).

What the code below does instead

The Python implementation skips link-walking entirely by pre-merging the lists at build time:

self.out[u] += self.out[self.fail[u]]   # u's matches = its own + everything its fail-target reports

BFS visits fail[u] before u, so out[fail[u]] is already complete. By search time out[she] is literally ['she', 'he'], and reporting is just "read the list" — same result, all work front-loaded.

Worked trace — search ushers

State starts at root (0). For each text character, take go(state, c), then report any patterns via the output-link chain.

Key moment is pos 4: she has no r edge, so we fell back via the failure link to he, which does have an r edge → her. No re-scanning of the text — that's the whole payoff.

Result: she, he, hers — every occurrence, found in one pass. ✅

Complexity

Crucially, the search cost is independent of the number of patterns — that's why it beats running a single-pattern matcher once per pattern.

Reference implementation (Python)

from collections import deque

class AhoCorasick:
    def __init__(self, patterns):
        # node 0 is the root
        self.next = [{}]          # next[v][c] -> child (real trie edges only)
        self.fail = [0]
        self.out  = [[]]          # patterns ending exactly at this node
        for p in patterns:
            self._add(p)
        self._build()

    def _new_node(self):
        self.next.append({})
        self.fail.append(0)
        self.out.append([])
        return len(self.next) - 1

    def _add(self, word):
        v = 0
        for c in word:
            if c not in self.next[v]:
                self.next[v][c] = self._new_node()
            v = self.next[v][c]
        self.out[v].append(word)

    def _build(self):
        q = deque()
        # depth-1 nodes fail to root
        for c, u in self.next[0].items():
            self.fail[u] = 0
            q.append(u)
        while q:
            v = q.popleft()
            for c, u in self.next[v].items():
                # failure link: parent's fallback, then follow c
                f = self.fail[v]
                while f and c not in self.next[f]:
                    f = self.fail[f]
                self.fail[u] = self.next[f].get(c, 0) if f or c in self.next[0] else 0
                if self.fail[u] == u:
                    self.fail[u] = 0
                # inherit outputs via the output link (merged for O(1) reporting)
                self.out[u] += self.out[self.fail[u]]
                q.append(u)

    def search(self, text):
        v, hits = 0, []
        for i, c in enumerate(text):
            while v and c not in self.next[v]:   # go(): fall back until an edge exists
                v = self.fail[v]
            v = self.next[v].get(c, 0)
            for w in self.out[v]:                # report every pattern ending here
                hits.append((i - len(w) + 1, w)) # (start index, pattern)
        return hits


ac = AhoCorasick(["he", "she", "his", "hers"])
print(ac.search("ushers"))
# [(1, 'she'), (2, 'he'), (2, 'hers')]   # (start index, pattern)

When to reach for it

• Virus/malware signature scanning, IDS/DDoS rules (match thousands of signatures in one stream pass)
• Spam / keyword / profanity filters
• Bioinformatics — finding many DNA/protein motifs in a genome
• Search highlighting, dictionary lookups, tokenizers

Rule of thumb: many fixed patterns, one (often huge) text → Aho–Corasick.

Mental model recap

1. Trie = all patterns sharing prefixes.
2. Failure links = "longest suffix that's still a valid prefix" — the KMP idea, multiplexed.
3. go() = trie edges + failure links → a complete automaton that never stalls.
4. Output links = report all (including overlapping) matches at each position.

Source: https://cp-algorithms.com/string/aho_corasick.html