Aho–Corasick Algorithm

Aho–Corasick algorithm is a multi-pattern dictionary string-matching algorithm in computation and algorithms, formal language theory, and information retrieval, invented by Alfred V. Aho and Margaret J. Corasick at Bell Labs in 1975. Given a finite dictionary of k pattern strings P = {p₁, p₂, …, p_k} of combined length m = ∑_i=1^k |p_i| over an alphabet Σ and a target text T of length n, the Aho–Corasick automaton locates all z occurrences of every pattern p_i within T in a single pass requiring O(m + n + z) time—independent of the number of patterns k.

Whereas running a single-pattern matcher such as the Knuth–Morris–Pratt algorithm (KMP) separately for each pattern in P would require O(m + kn) time, Aho–Corasick generalizes the KMP prefix-failure function from a single linear string to an entire prefix tree (trie) of patterns. Originally developed to accelerate Bibliographic Search libraries at Bell Labs and to power the Unix utility fgrep (fixed-string grep), the Aho–Corasick automaton remains a cornerstone of network intrusion detection systems (such as Snort and Suricata), antivirus signature scanners, bioinformatics peptide and k-mer matching alongside sequence alignment and Levenshtein distance, and lexical tokenization.

Let P = {p₁, …, p_k} ⊂ Σ⁺ be a non-empty set of patterns. The Aho–Corasick pattern-matching machine consists of a finite set of states Q (each corresponding uniquely to a prefix u of at least one pattern in P, with root state q₀ representing the empty string ε) governed by three functions:

1. Goto (Trie) function g(u, a): Directs state u along character a ∈ Σ to state ua if ua is a prefix of some pattern in P; for the root state q₀, g(q₀, a) = q₀ for every character a ∈ Σ that does not start any pattern in P.
2. Failure (Suffix Link) function f(u): For every state u ≠ q₀, f(u) points to the state v ∈ Q representing the longest proper suffix of u that is also a prefix of some pattern in P. Because |f(u)| < |u|, the failure links form a directed tree rooted at q₀ (the failure tree).
3. Output (Dictionary Link) function out(u): Associates each state u ∈ Q with the set of all dictionary patterns p_i ∈ P that are suffixes of the string u: out(u) = { p_i ∈ P : p_i is a suffix of u }.

Why Dictionary Suffix Links Are Needed

A pattern p_j ∈ P can be a proper substring of another pattern p_i ∈ P (for example, in the classic dictionary P = {he, she, his, hers}, the pattern he is a suffix of she). When the automaton reaches the trie node for she, it must report both she (which terminates at that node) and he (which terminates at the failure-link target of she). By precomputing a dictionary suffix link dict(u) pointing to the nearest ancestor of u in the failure tree that represents a complete pattern in P, all z_u matches ending at the current text position are emitted in O(z_u) time without traversing non-matching intermediate failure states.

Phase 1: Trie Construction and Phase 2: Breadth-First Failure Links

The automaton is built in two linear-time phases:

• Phase 1 (Keyword Trie): Insert each pattern p_i ∈ P character by character starting from the root q₀, creating new trie states as needed and adding p_i to out(u) at the terminal node u = p_i. This takes O(m) time where m = ∑ |p_i|.
• Phase 2 (BFS Failure & Output Links): All depth-1 states u = g(q₀, a) ≠ q₀ have their failure link set to the root: f(u) = q₀. The remaining states are visited in breadth-first search (BFS) order by increasing depth. For a state u with trie child v = g(u, a), the algorithm walks up the already-computed failure links of u—setting w ← f(u), then w ← f(w), and so on—until finding the first ancestor where g(w, a) is defined, and sets f(v) = g(w, a) and out(v) ← out(v) ∪ out(f(v)).

Potential-Function Proof of Linear O(m + n + z) Runtime

During text scanning of T = t₁t₂⋯t_n, let u_j denote the automaton state after processing character t_j. Advancing along a valid trie edge g(u, t_j) increases the trie depth |u| by at most +1 (at most n times across the entire text T). Conversely, every failure-link transition u ← f(u) strictly decreases the trie depth |u| by at least −1, and since |u| ≥ 0 always, the total number of failure transitions across all n characters cannot exceed n. Thus the total number of state transitions (trie advances plus failure jumps) over the entire text T is bounded by 2n, establishing O(n + z) scanning time. By an identical depth-potential argument along each pattern p_i during Phase 2, building all failure links takes at most 2m steps.

Complete Deterministic Finite Automaton (DFA) Optimization

To eliminate failure-link chasing altogether during real-time packet scanning, one can precompute the complete transition table δ(u, a) for every state u ∈ Q and every symbol a ∈ Σ during the BFS pass via:

δ(u, a) = g(u, a) if defined, else δ(f(u), a).

This converts the failure automaton into a complete deterministic finite automaton (DFA) that processes each text character in O(1) worst-case table lookup time at the cost of O(m |Σ|) memory (or O(m log |Σ|) when sparse child maps are stored in balanced trees or a skip list).

How does Aho–Corasick relate to the Knuth–Morris–Pratt (KMP) algorithm?

When the dictionary P contains only a single pattern (k = 1), the keyword trie is a simple unbranched chain of states 0, 1, …, m, and the Aho–Corasick failure function f(u) is identical to the KMP prefix function π[u]. Thus Aho–Corasick is the direct generalization of Knuth–Morris–Pratt from chains to trees.

Why can the output parameter z be as large as O(kn) in pathological inputs?

If P = {a, aa, aaa, …, a^k} and T = aⁿ, then every position j ≥ k in T matches all k patterns simultaneously, producing z = Θ(kn) total match events. Even in this case, if the caller only needs the count of matches or the longest match at each position, Aho–Corasick runs in O(m + n) time by accumulating pattern counts on each state during BFS preprocessing.

1. Aho, A. V., & Corasick, M. J. (1975). Efficient string matching: An aid to bibliographic search. Communications of the ACM, 18(6), 333–340. https://doi.org/10.1145/360825.360855
2. Commentz-Walter, B. (1979). A string matching algorithm fast on the average. Automata, Languages and Programming (ICALP 1979), 118–132. https://doi.org/10.1007/3-540-09510-1_10
3. Navarro, G., & Raffinot, M. (2002). Flexible Pattern Matching in Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences. Cambridge University Press. https://doi.org/10.1017/CBO9781316135228
4. Dori, S., & Landau, G. M. (2006). Construction of Aho Corasick automaton in linear time for integer alphabets. Information Processing Letters, 98(2), 66–72. https://doi.org/10.1016/j.ipl.2005.11.019