Lab 12 — Aho-Corasick Automaton

Goal

Match k patterns against a text simultaneously in O(|text| + Σ|patterns| + matches) — the multi-pattern generalization of KMP. Build the trie + failure links + output links, and know when a plain trie or naive scan is the smarter answer.

Background

Construction: insert all patterns into a trie. Then compute, for every trie node, a failure link: the deepest node whose path string is a proper suffix of the current node’s path string. Built by BFS — a node’s failure link is found by walking its parent’s failure chain until a node with the needed child exists (exactly the KMP prefix-function computation, lifted from a single string to a tree).

Output links: a match can end at a state without the state being a pattern’s endpoint — the pattern may be a suffix of the current path (e.g., state “she” must also report “he”). So each state needs the set of dictionary words reachable by following failure links. Either merge these sets during BFS, or keep a “dictionary suffix link” (nearest fail-ancestor that is a word) and chase the chain at match time.

Automaton view: goto (trie edges) + failure walking can be collapsed into a total transition function δ(state, char) — a dense table of size states × alphabet. Then scanning is one table lookup per character, no while-loop. Memory for speed.

KMP is Aho-Corasick with one pattern (phase-03 lab-05): the trie is a path, failure links are the prefix function.

Interview Context

  • Codeforces / ICPC: standard tool, appears with DP-on-automaton twists
  • Security / infra roles: genuinely production-relevant (Snort, ClamAV, WAFs run AC)
  • LC 1032 (Stream of Characters, Hard): AC is one clean answer; the reversed-word trie is the trick most solutions use
  • LC 1408 (String Matching in an Array, Easy): constraints so small naive wins — recognizing that IS the interview signal
  • Standard FAANG: rare; a trie question in disguise at most. KMP + trie (phase-03 labs 05/07) covers what you’ll actually face

When to Skip This Topic

Skip if any of these are true:

  • You haven’t internalized KMP’s prefix function — AC is that idea plus BFS, learn the base case first
  • You haven’t built a trie recently (phase-03 lab-07)
  • You’re not targeting competitive programming or security/text-scanning domains

If you can solve LC 1032 with the reversed-trie trick and explain why it works, you’ve extracted most of the interview value already.

Problem Statement

Multi-pattern search. Given patterns words = [w1..wk] and a text (possibly streamed one character at a time), report every occurrence of every pattern: pairs (end_index, word).

Anchor problems:

  • LC 1032 Stream of Characters: query(ch) appends a character; return true iff some word is a suffix of the stream so far.
  • LC 1408: find words that are substrings of other words — n ≤ 100, |word| ≤ 30. Naive in is O(n² · 30²) ≈ 10^7. Building AC here is over-engineering; say so.

Constraints

  • Σ|patterns| ≤ 2×10^5, |text| ≤ 10^6, lowercase letters
  • Overlapping and nested matches must all be reported
  • Stream variant: O(1) amortized per character after build

Clarifying Questions

  1. Can patterns duplicate or be suffixes/prefixes of each other? (Yes — this is exactly why output links exist.)
  2. Report all matches or just existence? (All, as (end_index, word); existence is the easy special case.)
  3. Is the pattern set fixed before the text arrives? (Yes — AC is a static structure; see follow-ups for dynamic.)
  4. Alphabet size? (26 here; affects dict-vs-array node representation and the dense-table option.)

Examples

patterns = ["he", "she", "his", "hers"], text = "ushers"
matches: (3, "she"), (3, "he"), (5, "hers")
        (indices are match END positions; "he" ends at index 3: u-s-h-e)

patterns = ["a", "aa", "aaa"], text = "aaaa"
matches: (0,a) (1,a) (1,aa) (2,a) (2,aa) (2,aaa) (3,a) (3,aa) (3,aaa)
— 9 matches from 4 chars: output size can dominate.

Brute Force

For each end position i and each pattern w, compare text[i+1−|w| : i+1] == w. O(|text| × k × maxlen). Fine for LC 1408’s constraints; hopeless at 10^6 × 10^5.

Brute Force Complexity

  • Time: O(|text| · Σ|patterns|)
  • Space: O(1) extra

Optimization Path

  1. Run KMP once per pattern: O(k · |text|) — still a factor k too slow.
  2. Trie of patterns, walk from every text position: O(|text| · maxlen) — re-scans overlapping windows.
  3. Aho-Corasick: one pass over the text; failure links carry over the longest useful suffix so no character is examined more than amortized O(1) times (plus output size).
  4. For LC 1032 specifically: the non-AC trick is a trie of reversed words, walking backward from the stream’s tail — O(maxlen) per query, no failure links. Simpler; worse when maxlen is large. AC gives O(1) amortized per query. Know both.

Final Expected Approach

from collections import deque

class AhoCorasick:
    def __init__(self):
        self.next = [{}]      # next[v]: char -> child state
        self.fail = [0]       # failure link
        self.out = [[]]       # words ending at v (own + inherited via fail)

    def add_word(self, word):
        v = 0
        for ch in word:
            if ch not in self.next[v]:
                self.next[v][ch] = len(self.next)
                self.next.append({})
                self.fail.append(0)
                self.out.append([])
            v = self.next[v][ch]
        self.out[v].append(word)

    def build(self):
        q = deque(self.next[0].values())      # depth-1 states: fail = root
        while q:
            u = q.popleft()
            for ch, v in self.next[u].items():
                q.append(v)
                f = self.fail[u]
                while f and ch not in self.next[f]:
                    f = self.fail[f]
                self.fail[v] = self.next[f].get(ch, 0)
                if self.fail[v] == v:
                    self.fail[v] = 0
                self.out[v] = self.out[v] + self.out[self.fail[v]]

    def feed(self, text):
        v = 0
        for i, ch in enumerate(text):
            while v and ch not in self.next[v]:
                v = self.fail[v]
            v = self.next[v].get(ch, 0)
            for w in self.out[v]:
                yield (i, w)                  # w ends at text[i]

class StreamChecker:                          # LC 1032 via AC
    def __init__(self, words):
        self.ac = AhoCorasick()
        for w in words:
            self.ac.add_word(w)
        self.ac.build()
        self.v = 0

    def query(self, ch):
        ac, v = self.ac, self.v
        while v and ch not in ac.next[v]:
            v = ac.fail[v]
        self.v = v = ac.next[v].get(ch, 0)
        return bool(ac.out[v])

Merging out lists during BFS trades memory (worst case a state inherits many words — think patterns a, aa, aaa, …) for zero match-time chasing. The alternative is a single dictionary-suffix link per state, chased at match time — same amortized output cost, O(states) memory. Say the tradeoff out loud.

Data Structures

  • Trie as parallel arrays: next (list of dicts), fail (int list), out (list of word lists)
  • BFS queue for build; current-state integer for scanning

Correctness Argument

  • Invariant: after consuming text[0..i], the state is the longest suffix of the consumed text that is a path in the trie. Failure walking preserves this: it discards the shortest possible prefix until a valid extension exists.
  • Failure links via BFS: a node’s fail target is strictly shallower, and BFS processes shallower nodes first, so fail[u] and its out are final before any child of u needs them.
  • No missed matches: any pattern occurrence ending at i is a suffix of the current state’s path string, hence reachable via the fail chain — captured in the merged out (or by chasing dictionary links).
  • Amortization: state depth increases by ≤1 per character and each fail step decreases it by ≥1 → total fail steps ≤ |text|.

Complexity

  • Build: O(Σ|patterns|) states; O(Σ|patterns| · alphabet) with dense tables, O(Σ|patterns|) expected with dicts
  • Scan: O(|text| + matches) amortized
  • Space: O(Σ|patterns|) states; merged output lists can add O(states × k) worst case — use dictionary links if that bites

Implementation Requirements

  • BFS (not DFS) for failure links — shallower-first is load-bearing
  • Depth-1 nodes fail to root explicitly; never let a node fail to itself
  • Report match END indices; start = end − len(word) + 1
  • Duplicate words: either dedupe on insert or accept duplicate reports — decide and state it
  • Stream variant must keep only the state integer between queries, not the text

Tests

  • [“he”,“she”,“his”,“hers”] × “ushers” → {(3,she), (3,he), (5,hers)}
  • Nested: [“a”,“aa”,“aaa”] × “aaaa” → 9 matches
  • LC 1032 example: words [“cd”,“f”,“kl”], stream “abcdefghijkl” → true exactly at d, f, l
  • Empty text → no matches; pattern absent from text → no matches
  • Stress: random pattern sets (1–6 words, length ≤ 4) over 2- and 3-letter alphabets vs the naive scanner — 400 trials, exact multiset equality

Follow-up Questions

  • Why must outputs follow failure links transitively? → A word can be a proper suffix of a state’s path without that state being its trie endpoint: at state “hers”, both “hers” and (via fail) “ers”→…→“s”-chain words may match. One fail hop isn’t enough — “hers”→“ers”→“rs”→“s” may each hold words. Merging during BFS (or chasing dictionary links that skip non-word states) makes reporting O(1) per actual match, so total cost is O(matches), not O(|text| · chain length).
  • Dense goto table vs on-the-fly failure walking? → Precomputing δ(state, char) for all chars gives branchless O(1) per character — right for hardware/regex engines and hot scanning loops — at states × alphabet memory (ruinous for Unicode). Failure walking is O(1) amortized with O(states) memory. Same asymptotics, different constants.
  • Count occurrences of every pattern in one pass without listing matches? → Increment a counter at the state reached per character; afterwards, propagate counters along failure links. Key insight: the fail links form a tree rooted at 0 (every link goes strictly shallower), so accumulate in reverse-BFS order, child into fail-parent. O(states) postprocessing, no per-match cost.
  • The dictionary changes online — insertions and deletions? → AC’s failure links are global; one insert can invalidate many. The standard workaround is log-structured: maintain ~log n automatons of doubling sizes, rebuild-merge on insert (amortized O(len · log n)), query all of them. Deletions: a parallel “negative” automaton, subtract counts.
  • Where does this run in production? → Snort/Suricata match thousands of intrusion signatures per packet with AC variants; ClamAV’s core scanner is AC; WAFs and DLP filters scan request bodies against rule sets; bioinformatics matches primer/adapter sets against reads. Multi-pattern scanning at line rate is AC’s home turf.
  • When is building AC the wrong call? → LC 1408-sized inputs (n ≤ 100, short words): naive in is simpler, obviously correct, and fast enough. Interviews reward matching the tool to the constraints, not maximal machinery.

Product Extension

  • Profanity/brand-safety filters over chat streams (the StreamChecker shape, literally)
  • Malware signature and IDS packet scanning
  • Log scanning for a large set of alert substrings in one pass
  • Keyword spotting over transcripts; entity gazetteer matching in NLP pipelines

Language/Runtime Follow-ups

  • Python: dict-based nodes are fine to Σ|patterns| ≈ 10^5; pyahocorasick (C extension) for real workloads.
  • C++: array nodes int next[26] + dense δ table is the contest standard; handles 10^6 text trivially.
  • Java: flatten nodes into int arrays; object-per-node GC pressure hurts at scale.
  • Go/Rust: cloudflare/ahocorasick, aho-corasick crate (the engine under ripgrep’s multi-literal matcher).

Common Bugs

  1. DFS instead of BFS for failure links: a child’s fail may point to a not-yet-processed node whose own fail/out is unset. Symptom: misses on deep overlapping patterns only.
  2. Missing output inheritance: reporting only out of exact trie endpoints — “she” matches but the “he” inside it is silently dropped. The single most common AC bug.
  3. Depth-1 self-loop: computing fail for root’s children via the generic walk can land a node on itself; then scanning loops forever on a mismatch.
  4. Off-by-one on match index: yielding start instead of end (or vice versa) — pick one, document it, test “ushers”.
  5. Resetting to root on mismatch: that’s the trie-walk-per-position brute force wearing AC’s clothes; correctness survives on some tests, complexity doesn’t.
  6. Stream variant re-walking the whole buffer per query: the entire point is carrying one state integer; O(len) per query means you rebuilt the naive solution.

Debugging Strategy

  • Print (node path-string, fail target path-string) for every node on [“he”,“she”,“his”,“hers”]; check each fail is the longest proper suffix that’s a trie path
  • Assert every fail target is strictly shallower than its node
  • Test the nested case [“a”,“aa”,“aaa”] first — it breaks bugs 1, 2, and 5 immediately
  • Diff against the naive scanner on random small-alphabet inputs before any performance test

Mastery Criteria

  • Build trie + BFS failure links from memory in ≤ 25 min
  • Explain why BFS order is required, in one sentence, without notes
  • Solve LC 1032 both ways (reversed trie, AC) in ≤ 35 min and articulate the tradeoff
  • State the amortized O(text + matches) argument (depth potential) on a whiteboard
  • Given LC 1408’s constraints, say “naive, and here’s why” in under a minute