Aho-Corasick — Multi-Pattern String Matching for FAANG Interviews

Problem Statement#

Given a text string and a set of pattern strings, find all occurrences of all patterns within the text simultaneously.

Constraints:

• Text length n can reach 10^5 or more
• Number of patterns k up to 10^3
• Total pattern length m up to 10^4
• Must not repeat work — naive k-pass KMP costs O(n * k)

Input:  text = "aabcdef", patterns = ["ab", "bc", "cd"]
Output: [("ab", index 1), ("bc", index 2), ("cd", index 3)]

Input:  text = "aabaab", patterns = ["aa", "ab", "aab"]
Output: [("aa",0), ("aab",0), ("ab",1), ("aa",3), ("aab",3), ("ab",4)]

Why This Problem Matters#

At Google, Amazon, and Cloudflare, multi-pattern search is not academic — it powers intrusion detection systems (Snort uses Aho-Corasick), search engines, and bioinformatics pipelines. When you have thousands of banned words or virus signatures to match, running KMP once per pattern costs O(n * k). Aho-Corasick reduces this to a single O(n + m + z) pass by building all patterns into a single automaton.

The algorithm is also a natural extension of KMP. If you understand the KMP failure function on a single string, you already understand the hard part — Aho-Corasick just applies the same idea to a trie of patterns.

The Core Insight#

Build a trie of all patterns. Each node in the trie represents a state "we have matched this prefix of some pattern". Then add failure links: if the current state fails to match the next character, jump to the longest proper suffix of the current state that is also a prefix of some pattern in the trie.

This is exactly the KMP failure function, generalized to a trie. Once failure links are built (via BFS from the root), streaming text through the automaton costs O(1) amortized per character.

Output links propagate pattern matches: if a state's failure link points to a state that is the end of a pattern, that pattern also matches at the current position.

Visual Dry Run#

Patterns: ["he", "she", "his", "hers"]

Trie structure after insertion:

root → h → e[end:"he"] → r → s[end:"hers"]
     → s → h → e[end:"she"]
     → h → i → s[end:"his"]

Failure links (BFS):

• State "h": fail → root
• State "he": fail → root (no proper suffix "e" in trie)
• State "s": fail → root
• State "sh": fail → "h" (suffix "h" exists in trie)
• State "she": fail → "he" (suffix "he" exists and is end of pattern)

When streaming "ushers", the automaton visits 6 states and reports "she", "he", "hers" in a single pass.

Solution (Optimal)#

from collections import deque
 
class AhoCorasick:
    def __init__(self, patterns):
        self.goto = [{}]      # goto[state][char] = next state
        self.fail = [0]       # failure link for each state
        self.output = [[]]    # pattern indices ending at each state
        for i, p in enumerate(patterns):
            self._insert(p, i)
        self._build_fail()
 
    def _insert(self, pattern, idx):
        node = 0
        for c in pattern:
            if c not in self.goto[node]:
                self.goto[node][c] = len(self.goto)
                self.goto.append({})
                self.fail.append(0)
                self.output.append([])
            node = self.goto[node][c]
        self.output[node].append(idx)
 
    def _build_fail(self):
        q = deque()
        # Depth-1 nodes: failure link always points to root
        for c, s in self.goto[0].items():
            self.fail[s] = 0
            q.append(s)
        while q:
            r = q.popleft()
            for c, s in self.goto[r].items():
                q.append(s)
                # Walk up failure links to find longest matching suffix in trie
                state = self.fail[r]
                while state and c not in self.goto[state]:
                    state = self.fail[state]
                self.fail[s] = self.goto[state].get(c, 0)
                if self.fail[s] == s:
                    self.fail[s] = 0   # avoid self-loops at root
                # Propagate output: inherit matches from failure link
                self.output[s] += self.output[self.fail[s]]
 
    def search(self, text):
        state = 0
        results = []
        for i, c in enumerate(text):
            # Walk failure links until we find a match or reach root
            while state and c not in self.goto[state]:
                state = self.fail[state]
            state = self.goto[state].get(c, 0)
            # Report all patterns ending at this position
            for pattern_idx in self.output[state]:
                results.append((i, pattern_idx))
        return results

function buildAhoCorasick(patterns) {
    const goto_ = [new Map()];
    const fail = [0];
    const output = [[]];
 
    // Insert all patterns into trie
    for (let i = 0; i < patterns.length; i++) {
        let node = 0;
        for (const c of patterns[i]) {
            if (!goto_[node].has(c)) {
                goto_[node].set(c, goto_.length);
                goto_.push(new Map());
                fail.push(0);
                output.push([]);
            }
            node = goto_[node].get(c);
        }
        output[node].push(i);
    }
 
    // BFS to build failure links
    const q = [];
    for (const [c, s] of goto_[0]) {
        fail[s] = 0;
        q.push(s);
    }
    let head = 0;
    while (head < q.length) {
        const r = q[head++];
        for (const [c, s] of goto_[r]) {
            q.push(s);
            let state = fail[r];
            while (state && !goto_[state].has(c)) {
                state = fail[state];
            }
            fail[s] = goto_[state].get(c) ?? 0;
            if (fail[s] === s) fail[s] = 0;
            output[s] = [...output[s], ...output[fail[s]]];
        }
    }
 
    return { goto: goto_, fail, output };
}
 
function search(text, { goto: goto_, fail, output }) {
    let state = 0;
    const results = [];
    for (let i = 0; i < text.length; i++) {
        const c = text[i];
        while (state && !goto_[state].has(c)) {
            state = fail[state];
        }
        state = goto_[state].get(c) ?? 0;
        for (const patIdx of output[state]) {
            results.push([i, patIdx]);
        }
    }
    return results;
}

Time: O(m) build trie + O(m) build failure links + O(n + z) search = O(n + m + z) Space: O(m * ALPHABET_SIZE) for the trie nodes

Complexity Analysis#

Key advantage over k separate KMP runs: O(n + m + z) vs O(n * k + m).

Common Mistakes#

• Forgetting output link propagation. When you reach a state that is the end of pattern A, its failure link may point to a state that is the end of pattern B. Without propagating output[s] += output[fail[s]], you miss matches for patterns whose ends are suffixes of other patterns.
• Self-loop at root in failure links. A depth-1 state's failure link points to root. If you incorrectly set fail[s] = s for a root child, you get infinite loops in search.
• Not handling the case where a character is not in root's goto. When state = 0 and c not in goto[0], stay at root (return 0), do not loop.
• BFS order matters. Failure links must be built BFS level by level so that when you set fail[s], the failure link of its parent is already correct.

Interview Tips#

• Start by explaining Aho-Corasick as "KMP failure function applied to a trie instead of a string".
• Draw the trie for a small example (2-3 short patterns) and walk through failure link construction.
• Mention the real-world use cases: anti-spam, IDS (intrusion detection), DNA sequence search.

Follow-up Questions#

• How would you extend this to handle wildcard patterns like he*o? Add NFA states for wildcards and use subset construction to build a DFA. The automaton becomes more complex but the streaming principle is the same.
• What if patterns can be updated dynamically (add/remove)? Rebuilding from scratch is O(m). Incremental updates are complex. In practice, systems batch updates and rebuild periodically.
• How does this compare to Rabin-Karp for multi-pattern search? Rabin-Karp achieves expected O(n + m) using rolling hashes but has worst-case O(n * k) on hash collisions. Aho-Corasick has guaranteed O(n + m + z).

Key Takeaways#

• Aho-Corasick matches all k patterns simultaneously in a single pass over the text in O(n + m + z) — no need to run KMP k separate times.
• The algorithm builds a trie of all patterns then adds KMP-style failure links via BFS from the root.
• Failure links point to the longest proper suffix of the current trie state that also appears in the trie.
• Output links propagate pattern matches: if a state's failure link points to a pattern end, that match is also reported.
• BFS level-order construction ensures each failure link is computed only after its parent's failure link is already set.
• Real-world systems (Snort IDS, search engines, bioinformatics) use Aho-Corasick exactly because of its O(n + m + z) guarantee.
• If you can explain the KMP failure function, you can derive Aho-Corasick — it is the same idea one level of abstraction higher.