Aho-Corasick Multi-Pattern Automaton Scanner

Unifying Tries and KMP Prefix Automata

Scanning a text of length $|T|$ against $k$ patterns of total length $M = \sum |P_i|$ naively takes $O(k \cdot |T|)$. The Aho-Corasick automaton (1975) achieves $O(M + |T| + z)$ worst-case time—independent of the number of patterns $k$—by augmenting a keyword Trie with two sets of directed links:

Failure Links (fail[u]): Point to the longest proper suffix of the string represented by node $u$ that also exists as a prefix in the Trie. Computed in $O(M)$ time via level-order BFS.
Dictionary Output Links (outputLink[u]): Point directly to the longest proper suffix of $u$ that is a complete dictionary pattern. Without outputLink, traversing fail links at every character could visit $O(M)$ non-matching internal nodes; with outputLink, every step visits only actual matches in $O(1)$ per reported occurrence $z$.

Amortized Analysis of Text Scanning

Just as in KMP, each character of $T$ increases the current node depth by at most $1$, while every failure-link transition strictly decreases the node depth. Thus the total number of failure transitions across the entire text scan is bounded by $|T|$.

Curriculum Connections

Aho-Corasick Multi-Pattern Automaton
Tries, Radix Trees & Ternary Search Trees
KMP & Prefix-Function Automata

Guided Implementation Walkthrough (4 Progressive Steps)

Step 1: Keyword Trie Insertion

Core Mechanical Concept: Keyword Trie Insertion
Target Module: index.js (Step1)
Engineering Specification: Implement addPattern(pattern) to insert each pattern character-by-character into this._nodes and record the pattern index in the terminal node's outputs list.
Verification Invariant: verifies Step 1: Keyword Trie Insertion

Step 2: BFS Failure Links & Dictionary Output Links

Core Mechanical Concept: BFS Failure Links & Dictionary Output Links
Target Module: index.js (Step2)
Engineering Specification: Implement compile() using level-order BFS so every node v (child of u via ch) resolves fail[v] from fail[u] and sets outputLink[v] to the nearest proper suffix state that is a dictionary word.
Verification Invariant: verifies Step 2: BFS Failure Links & Dictionary Output Links

Step 3: Amortized O(1) Automaton Transitions

Core Mechanical Concept: Amortized O(1) Automaton Transitions
Target Module: index.js (Step3)
Engineering Specification: Implement _step(state, ch) to climb failure links when a character transition is absent.
Verification Invariant: verifies Step 3: Amortized O(1) Automaton Transitions

Step 4: Multi-Pattern Stream Harvesting

Core Mechanical Concept: Multi-Pattern Stream Harvesting
Target Module: index.js (Step4)
Engineering Specification: Implement search(text) to step through text once and follow outputLink pointers to emit all overlapping pattern matches in $O(|T| + z)$ time.
Verification Invariant: verifies Step 4: Multi-Pattern Stream Harvesting

Asymptotic & Memory Layout Guarantees

Category: Strings & Automata
Difficulty: Advanced (~45 minutes)
Key Architectural Highlights:
• Trie construction with BFS failure-link synthesis generalizing KMP to dictionaries
• Dictionary suffix shortcuts (outputLinks) avoiding O(m) failure-chain traversal on sparse matches
• Deterministic DFA transition table compilation guaranteeing O(1) per-character text scanning
Tags & Primitives: Aho-Corasick, Trie, Failure Links, Dictionary Links, Multi-Pattern Search

Production Systems Context & Verification

This from-scratch implementation is engineered with zero external dependencies and deterministic verification harnesses. Every internal invariant—from pointer restoration and bitmask addressing to amortized potential bounds and tree height balance—is asserted directly in test.js. Use the interactive browser workbench above to complete the guided steps in Guided Lab mode or inspect and benchmark the complete reference architecture in Full Solution mode.

Code & Verify in the Browser Workbench