Aho-Corasick Automaton (Multi-Pattern Matching)

This is an extension topic beyond most interviews; it pays off when many patterns must be found in one text or stream (banned-word filters, "stream of characters", counting dictionary words in a document) and running KMP once per pattern is too slow.

Intuition

KMP matches one pattern in linear time by remembering, after a mismatch, the longest suffix of what was read that is still a prefix of the pattern. Aho-Corasick does the same for many patterns at once:

1. Insert all patterns into a trie. Each trie node is a state: "the last characters read spell this prefix of some pattern".
2. Give every node a failure link: the node for the longest proper suffix of its string that is also a prefix of some pattern (that is, a node in the trie). It is exactly KMP's prefix function, generalized from one string to a whole trie, and it is built level by level with BFS: the failure of child v = u + c is found by following failures from fail(u) until some node has a c child.
3. Scan the text. On character c, move to the c child if it exists; otherwise follow failure links until one does (or you are back at the root). The current node is always the longest suffix of the text read so far that is a prefix of some pattern.

A pattern ends at the current position if it ends at the current node or at any node on its failure chain (a shorter suffix). Two ways to collect them:

• Output links: precompute for each node the nearest node on its failure chain that ends a pattern; follow only those, so the cost is proportional to the number of reported matches.
• Counting: if you only need how many times each pattern occurs, add 1 to the current node at each step and, at the end, push the counts up the failure links from deep nodes to shallow ones.

When to use it in interviews / OAs

• "Report all positions where any of these words occurs in the text."
• "Stream of characters": after each new letter, does some dictionary word end here?
• Censoring or flagging text against a large banned-word list.
• "How many times does each keyword appear?" across one long document.
• If the patterns are few or very short (say length up to 10), a reversed trie walked backwards from each position, or hashing, is often simpler and good enough.

Template

from collections import deque


class AhoCorasick:
    def __init__(self, patterns: list[str]):
        # patterns must be non-empty strings
        self.lens = [len(p) for p in patterns]
        self.children: list[dict[str, int]] = [{}]
        self.ends: list[list[int]] = [[]]  # ids of patterns ending exactly at each node
        for pid, p in enumerate(patterns):
            node = 0
            for ch in p:
                if ch not in self.children[node]:
                    self.children[node][ch] = len(self.children)
                    self.children.append({})
                    self.ends.append([])
                node = self.children[node][ch]
            self.ends[node].append(pid)
        n = len(self.children)
        self.fail = [0] * n
        self.out = [-1] * n  # nearest node on the failure chain (itself included) ending a pattern
        self.order = []  # BFS order: parents and failure targets come first
        q = deque(self.children[0].values())
        for v in q:
            self.out[v] = v if self.ends[v] else -1
        while q:
            u = q.popleft()
            self.order.append(u)
            for ch, v in self.children[u].items():
                self.fail[v] = self.step(self.fail[u], ch)  # same idea as KMP's fallback
                self.out[v] = v if self.ends[v] else self.out[self.fail[v]]
                q.append(v)

    def step(self, state: int, ch: str) -> int:
        while state and ch not in self.children[state]:
            state = self.fail[state]
        return self.children[state].get(ch, 0)

    def find_all(self, text: str) -> list[tuple[int, int]]:
        # (start index, pattern id) for every occurrence
        res, state = [], 0
        for i, ch in enumerate(text):
            state = self.step(state, ch)
            node = self.out[state]
            while node != -1:  # visit only nodes where some pattern ends
                for pid in self.ends[node]:
                    res.append((i - self.lens[pid] + 1, pid))
                node = self.out[self.fail[node]]
        return res

    def count_each(self, text: str) -> list[int]:
        # occurrences per pattern, without listing them
        hits = [0] * len(self.children)
        state = 0
        for ch in text:
            state = self.step(state, ch)
            hits[state] += 1
        for u in reversed(self.order):  # deep to shallow: push counts along failure links
            hits[self.fail[u]] += hits[u]
        counts = [0] * len(self.lens)
        for u, ids in enumerate(self.ends):
            for pid in ids:
                counts[pid] = hits[u]
        return counts


class StreamChecker:
    # after each query(ch): does any word end at the newest character?
    def __init__(self, words: list[str]):
        self.ac = AhoCorasick(words)
        self.state = 0

    def query(self, ch: str) -> bool:
        self.state = self.ac.step(self.state, ch)
        return self.ac.out[self.state] != -1

Complexity

Let L be the total length of all patterns, n the text length and z the number of reported matches. Building the trie and the failure links costs O(L) dictionary operations (amortized over each pattern, exactly as in KMP). Scanning is O(n) amortized, plus O(z) for find_all; count_each adds O(L) for the final push. Memory is O(L) nodes. With a fixed alphabet you can precompute a full transition table (O(L * alphabet) memory) so each step is O(1) without the while loop.

Common pitfalls

• Stopping at the current node. Patterns that are suffixes of the current match (for example "he" inside "she") end at nodes on the failure chain; without output links or count propagation they are missed.
• Walking the whole failure chain at every character. For patterns like a, aa, aaa, ... that is O(n * L); use output links (to report) or the reverse-BFS push (to count).
• Building failure links in DFS order. A node's failure target must already be finished; BFS by depth guarantees it.
• Duplicate patterns. Several ids can end at the same node; store a list, not a single id.
• Empty patterns. They would end at the root and match everywhere; reject them or handle them separately.
• Resetting state between queries. In streaming use, keep the state across calls; resetting it loses matches that span several queries.

Interview variations

• Stream of characters. StreamChecker above; the reversed-trie solution also works when words are short.
• Multi-keyword highlighting / bold words in a string. find_all gives intervals; merge them.
• Count each keyword. count_each in O(n + L).
• Longest substring avoiding forbidden words. Track, for every end position, the latest start that makes some forbidden word end here, using the matches from the automaton; then a sliding window.
• Counting strings that avoid all patterns. DP over (length, automaton state) where states that end a pattern are forbidden; contest-style, occasionally seen in hard rounds.