Aho-Corasick Multi-Pattern Matching

Aho-Corasick Multi-Pattern Matching

Mathematical Definition

Let D = (p₀, …, p_k−1) be an ordered list of distinct, nonempty words, and let T be a text over an alphabet Σ. Every distinct dictionary prefix, including the empty prefix ε, is a trie state. The root represents ε.

For a nonroot state v with prefix w(v), the failure target f(v) is the state representing the longest proper suffix of w(v) that is also a dictionary prefix. Such a state always exists because ε is a suffix. We assign f(root) = root as an implementation sentinel; the root does not have a proper suffix.

Each interval has zero-based, inclusive endpoints. The complete output list contains every dictionary word that is a suffix of the state's prefix. This demonstration orders outputs by the original dictionary order, so simultaneous matches have a deterministic order.

Key Concepts

Construction in breadth-first order

Insert all patterns into the trie. A child of the root has the root as its failure target. For an edge v → u labeled c at greater depth, start from f(v) and find the transition on c, following failure links as necessary. The result is f(u). Breadth-first construction processes shorter prefixes first, so the failure target's outputs can be inherited immediately. This implementation also completes a 26-letter transition table at each state during construction.

Search without rewinding the text

When a trie edge on the next text character exists, take it. Otherwise, follow the failure link and retry the same character. Continue until a matching edge is found or the root is reached. At the root, a missing edge leaves the scan at the root. After consuming the character, emit all outputs of the resulting state.

After any number of consumed characters, the scan state represents the longest suffix of the consumed text that is a dictionary prefix. Failure jumps only shorten this suffix; they do not consume a character or move the text cursor backward. A single replay step therefore consumes one character even when it follows several failure links.

Suffix outputs and overlapping matches

For the dictionary (he, she, his, hers), the state she fails to he and emits both he and she. In ushers these matches are he [2, 3] and she [1, 3]. The next character r follows the failure link to he and then the r edge to her; the final s reports hers [2, 5].

For (a, aa, aaa) in aaaa, each ending position emits all applicable suffix words. The four positions produce 1 + 2 + 3 + 3 = 9 occurrences. This is standard all-match behavior. A leftmost or nonoverlapping policy would deliberately suppress some occurrences and is a different matching policy.

Complexity and the replay interface

Let L be the sum of pattern lengths, S the number of trie states, n the text length, and z the number of reported occurrences. S ≤ L + 1. With constant-time edge lookup, core search takes O(n + z) time: trie transitions increase depth by one, and failure transitions decrease depth, bounding the total number of failure jumps by O(n). A completed transition table can instead consume each character with a single lookup.

This demonstration uses O(26S) table storage and construction work, plus materialized output lists. If Q is the sum of all stored output-list lengths, copying these lists costs O(Q); arranging their dictionary order also incurs sorting work. The teaching replay stores n + 1 frames, their failure jumps, and one shared list of z occurrences, requiring O(n + z) additional space. Rendering tables and the currently visible occurrence log adds interface work beyond the core search bound. Production implementations can use output links to avoid copying a full output closure into every state.

Declared input and reset policies

The controls accept 1–6 distinct lowercase ASCII words, each 1–8 letters, with at most 24 letters in total. LF and CRLF separate words. Empty lines, duplicate patterns, uppercase letters, spaces, punctuation and non-ASCII characters are rejected; inputs are never trimmed, case converted, deduplicated or truncated. Text may be empty and otherwise contains up to 60 lowercase ASCII letters. General Aho-Corasick implementations can support other alphabets and empty-pattern conventions.

Editing either input resets the scan and stops playback. Invalid input hides the previous automaton and results. Reset scan keeps the dictionary, text, inspection and diagram navigation. Reset inputs restores the example and all settings. Reset view changes only the pan offset; Reset node layout changes only dragged node positions. Rewinding the scan removes occurrences emitted by later characters.

Historical Context

Alfred V. Aho and Margaret J. Corasick introduced the algorithm in their 1975 paper, “Efficient String Matching: An Aid to Bibliographic Search.” Their construction combines goto, failure and output functions to find many keywords in one pass through a text. The paper's classic (he, she, his, hers) example illustrates why following failure links must preserve suffix outputs.

Real-world Applications

• Keyword search: scan documents for a fixed dictionary of terms while reporting every occurrence.
• Signature detection: recognize many fixed byte sequences in logs or network payloads when the appropriate byte alphabet is used.
• Sequence analysis: locate an exact dictionary of motifs in a sequence, with overlaps retained.
• Lexical tools: use a reusable dictionary automaton to locate candidate tokens before applying domain-specific selection rules.

The algorithm performs exact matching. Approximate search, case folding, Unicode normalization and word-boundary rules require additional choices outside this demonstration.

Related Concepts

• Trie: shares dictionary prefixes and supports exact or prefix queries.
• KMP String Matching: reuses proper prefix-suffix borders for one pattern.
• Suffix Array: preprocesses a text's suffixes for substring queries.
• Finite State Machine: models state transitions; Aho-Corasick constructs a particular machine from a dictionary.

References

• Aho and Corasick (1975), Efficient String Matching: An Aid to Bibliographic Search, Communications of the ACM 18(6), 333–340, DOI: 10.1145/360825.360855.
• NIST Dictionary of Algorithms and Data Structures: Aho-Corasick.
• Rust aho-corasick library: implementation design.
• Rust aho-corasick library: standard and leftmost matching policies.