Aho-Corasick

The Aho-Corasick algorithm generalizes Knuth-Morris-Pratt from one pattern to many. Given a dictionary of k patterns whose lengths sum to m, and a text of length n, it reports every occurrence of every pattern in O(n + m + z) time, where z is the total number of pattern occurrences in the text. The construction has two phases: first, build a Trie over the patterns; second, decorate that trie with failure links that, like KMP’s failure function, point to the longest proper suffix of the current node’s matched string that is itself a prefix of some pattern. The result is a deterministic automaton: feed it text one character at a time, follow goto and failure transitions, and report matches whenever the current state (or any state reachable via failure links) is the end of a dictionary pattern. Aho and Corasick published the algorithm in 1975 to speed up bibliographic search at Bell Labs (“a librarian wants every reference to any of these 5,000 keywords”). It remains the canonical engine for virus scanners, intrusion detection systems (fgrep-style multi-pattern matching, Snort/Suricata signature engines), grep -F with multiple patterns, content-filtering firewalls, and academic plagiarism detectors.

1. Intuition — A Single Walk That Watches for Every Word

Imagine a security guard who has memorized a list of 5,000 banned words and has to scan a continuous loudspeaker broadcast for any of them. A naive guard would, on every new syllable, mentally rewind through the last few syllables and check whether they match the start of any of the 5,000 words — quadratic in pain. A good guard maintains a single mental state at all times that says: “of all 5,000 words, the one I’m currently making the most progress through is FOO and I’ve matched its first 4 letters.” When a new syllable arrives, the guard tries to extend the match. If extension fails, the guard doesn’t restart from scratch — he asks: “given the last 4 syllables I just heard, what’s the longest suffix of those syllables that is also the start of any other word in my list?” That fallback is the failure link. He resumes from that fallback state and tries again with the new syllable.

Aho-Corasick is exactly that guard, mechanized. The trie is the guard’s memory of all possible word-prefixes; failure links are the precomputed fallbacks for every situation. Once built, scanning the broadcast is a single linear walk through the text — never revisiting a character, never rewinding.

The key generalization over Knuth-Morris-Pratt: KMP has one pattern, so its failure function maps “I’ve matched q characters of the pattern” to “back off to q' < q characters of the same pattern.” Aho-Corasick has many patterns sharing prefixes through a trie, so its failure link maps “I’m at trie node v (which spells out string s)” to “back off to trie node u whose string is the longest proper suffix of s that is itself the spelling of some trie node.” The “itself the spelling of some trie node” condition is exactly “a prefix of one of the patterns.” So failure links generalize from “longest proper suffix that’s also a prefix of the pattern” to “longest proper suffix that’s also a prefix of some pattern.”

2. Tiny Worked Example

Take patterns P = {"he", "she", "his", "hers"} (sums to m = 11 characters) and text T = "ushers" (length n = 6).

2.1 Build the trie

Insert each pattern as a path from the root. Numbering nodes in BFS order (root = 0):

            (0)
           /    \
          h      s
         (1)    (3)
        /  \      \
       e    i      h
      (2)  (6)    (4)
       |    |      |
       r    s      e
      (8)  (7)    (5)
       |
       s
      (9)

Node-to-string mapping:

• 0: ""
• 1: "h"
• 2: "he" ← pattern endpoint (output: "he")
• 3: "s"
• 4: "sh"
• 5: "she" ← pattern endpoint (output: "she")
• 6: "hi"
• 7: "his" ← pattern endpoint (output: "his")
• 8: "her"
• 9: "hers" ← pattern endpoint (output: "hers")

The four “pattern endpoint” nodes are marked as accepting states; each carries an output set (in this small example, exactly one pattern per accepting node, but in general a node can output multiple patterns — see §6.2).

2.2 Compute failure links via BFS

The failure link of a node v (with depth ≥ 2) points to the deepest other trie node whose spelling is a proper suffix of v’s spelling. Depth-1 nodes (children of root) and the root itself fail back to the root. We compute failure links via BFS so that every node’s parent-failure has already been resolved when we visit the node.

Walking through:

Node	String	Failure link	Reasoning
0	""	(none)	root
1	"h"	0	depth 1 → root
3	"s"	0	depth 1 → root
2	"he"	0	proper suffixes: "e", "". "e" is not in trie. Fall back to root.
6	"hi"	0	proper suffixes: "i", "". Neither indexes a trie node except root.
4	"sh"	1	proper suffixes: "h", "". "h" is node 1.
8	"her"	0	proper suffixes: "er", "r", "". None except root.
7	"his"	3	proper suffixes: "is", "s", "". "s" is node 3.
5	"she"	2	proper suffixes: "he", "e", "". "he" is node 2 — note this is itself an accepting state!
9	"hers"	3	proper suffixes: "ers", "rs", "s", "". "s" is node 3.

Notice node 5’s failure link points to node 2, which is itself a pattern endpoint. This is critical: when we arrive at node 5 (matching "she"), we have also matched "he". We must report both. The standard implementation handles this with dictionary suffix links (a.k.a. output links) that point each node to the nearest accepting ancestor along the failure chain (§3.4).

2.3 Search trace

Walk through T = "ushers" keeping current state s (a trie node, starting at root). For each text character c:

1. While there’s no goto(s, c) and s is not root: s ← failure(s).
2. If goto(s, c) exists: s ← goto(s, c).
3. Walk the dictionary-suffix-link chain from s and emit every accepting state’s outputs.

i	T[i]	Before state	After goto	After fail-walk	Outputs
0	u	0	no goto from 0 on u; stay at 0	0	—
1	s	0	goto(0, s) = 3	3	—
2	h	3	goto(3, h) = 4	4	—
3	e	4	goto(4, e) = 5	5	"she" (state 5), "he" (via dict-suffix-link to state 2)
4	r	5	no goto(5, r); fail to state 2 ("he"); no goto(2, r); fail to state 0; no goto(0, r); stay 0	0	—
5	s	0	goto(0, s) = 3	3	—

Wait — that misses "hers". Let me re-trace step 4 more carefully. After state 5, character r:

• goto(5, r): state 5 has no r child. Follow failure link to state 2.
• At state 2 ("he"), goto(2, r): state 2 has child r → state 8. So s ← 8.

Corrected trace:

i	T[i]	Before	After step 1+2	Outputs
0	u	0	0	—
1	s	0	3	—
2	h	3	4	—
3	e	4	5	"she" at state 5; "he" via dict-suffix to state 2
4	r	5	fail(5)=2, goto(2, r)=8, so 8	—
5	s	8	goto(8, s)=9, so 9	"hers" at state 9

Three matches: "she" and "he" ending at index 3, "hers" ending at index 5. The text was scanned in a single left-to-right walk; characters were never re-examined. That linearity is the algorithm’s whole point.

3. Algorithm / Pseudocode

The algorithm has three procedures: trie construction, failure-link computation (BFS), and online search.

3.1 Trie construction

BuildTrie(patterns):
    root := new node
    for each pattern P with index p in patterns:
        v := root
        for each character c in P:
            if goto(v, c) is undefined:
                goto(v, c) := new node
            v := goto(v, c)
        v.output.add(p)              # mark as accepting state for pattern p
    return root

Time: O(m) where m = total pattern length. Space: O(m · |Σ|) if goto is stored as a hash/array; O(m) if as a linked list of (char, child) pairs at each node.

3.2 Failure-link construction (BFS)

BuildFailureLinks(root):
    queue := empty queue
    for each child c of root:
        c.failure := root
        queue.enqueue(c)
    while queue is not empty:
        v := queue.dequeue()
        for each (char, u) in v.children:
            queue.enqueue(u)
            f := v.failure
            while f != root and goto(f, char) is undefined:
                f := f.failure
            if goto(f, char) is defined and goto(f, char) != u:
                u.failure := goto(f, char)
            else:
                u.failure := root
            # Dictionary-suffix-link (a.k.a. output link)
            if u.failure.output is non-empty:
                u.dict_suffix := u.failure
            else:
                u.dict_suffix := u.failure.dict_suffix     # may be null

The dict_suffix precomputation lets the search step emit all matches in time proportional to the number of matches at this state, not the length of the failure chain.

Time: O(m · |Σ|) in the worst case for dense alphabets, or O(m) with hashed transitions and amortized analysis (the inner while is amortized O(1) per node by the same potential argument as KMP — each step up a failure link is later paid for by a step-down via a goto edge).

3.3 Online search

Search(root, T):
    s := root
    matches := []
    for i in 0 .. |T|-1:
        c := T[i]
        while s != root and goto(s, c) is undefined:
            s := s.failure
        if goto(s, c) is defined:
            s := goto(s, c)
        # Walk the dictionary-suffix-link chain to emit ALL matches ending at i
        u := s
        while u != null:
            for p in u.output:
                matches.append( (p, i - len(patterns[p]) + 1) )
            u := u.dict_suffix
    return matches

Time: O(n + z) where z = total matches. The amortized analysis (§5) bounds the inner while over all iterations by O(n).

3.4 Goto-function variant: building a full DFA

The pseudocode above keeps goto as the “tree edges of the trie” and uses the failure link to handle missing transitions. An equivalent formulation precomputes a complete goto* function (the automaton form) by, for each (state, char) pair, following failure links until a defined goto is found, then caching the result. After this preprocessing the inner while loop in search disappears: every transition is a single table lookup. Construction time becomes O(m · |Σ|) and the search loop is straight-line O(n + z). This is what production virus scanners ship — they pay the construction cost once at startup and run search at memory-bandwidth speed.

4. Python Implementation

A complete, runnable Aho-Corasick matcher with failure links, dictionary-suffix-links, and overlapping-match reporting:

from collections import deque
from typing import Iterable
 
class AhoCorasick:
    """Aho-Corasick multi-pattern matcher.
 
    After `add_pattern` calls, call `build()` to compute failure links.
    Then `search(text)` yields (pattern_index, start_index_in_text) tuples
    for every occurrence of every pattern (overlaps included).
    """
 
    def __init__(self) -> None:
        # Each node is a dict: {char -> child_index}.
        self.goto: list[dict[str, int]] = [dict()]
        self.failure: list[int] = [0]
        self.dict_suffix: list[int] = [0]   # 0 means "no further dict ancestor"
        self.output: list[list[int]] = [[]]  # pattern indices ending at this node
        self.patterns: list[str] = []
 
    def add_pattern(self, pattern: str) -> None:
        """Insert `pattern` into the trie. Returns the assigned pattern index."""
        node = 0
        for ch in pattern:
            if ch not in self.goto[node]:
                self.goto.append(dict())
                self.failure.append(0)
                self.dict_suffix.append(0)
                self.output.append([])
                self.goto[node][ch] = len(self.goto) - 1
            node = self.goto[node][ch]
        self.output[node].append(len(self.patterns))
        self.patterns.append(pattern)
 
    def build(self) -> None:
        """Compute failure and dict-suffix links via BFS over the trie."""
        q: deque[int] = deque()
        # Depth-1 nodes (root's children) all fail to root.
        for ch, child in self.goto[0].items():
            self.failure[child] = 0
            q.append(child)
        while q:
            v = q.popleft()
            for ch, u in self.goto[v].items():
                q.append(u)
                # Walk failure chain from v's failure to find a node with `ch` transition.
                f = self.failure[v]
                while f != 0 and ch not in self.goto[f]:
                    f = self.failure[f]
                self.failure[u] = self.goto[f].get(ch, 0)
                if self.failure[u] == u:
                    # Self-loop guard: only happens if root had `ch`-child equal to u itself,
                    # which means u is a depth-1 node already handled above.
                    self.failure[u] = 0
                # Dict-suffix: nearest accepting ancestor along failure chain.
                fu = self.failure[u]
                if self.output[fu]:
                    self.dict_suffix[u] = fu
                else:
                    self.dict_suffix[u] = self.dict_suffix[fu]
 
    def search(self, text: str) -> Iterable[tuple[int, int]]:
        """Yield (pattern_index, start_index) for every match (overlaps included)."""
        s = 0
        for i, ch in enumerate(text):
            while s != 0 and ch not in self.goto[s]:
                s = self.failure[s]
            s = self.goto[s].get(ch, 0)
            # Walk dict-suffix chain to emit every match ending at position i.
            u = s
            while u != 0:
                for p in self.output[u]:
                    yield (p, i - len(self.patterns[p]) + 1)
                u = self.dict_suffix[u]
 
 
# Worked example from §2:
ac = AhoCorasick()
for w in ["he", "she", "his", "hers"]:
    ac.add_pattern(w)
ac.build()
matches = sorted(ac.search("ushers"))
# Patterns: 0=he, 1=she, 2=his, 3=hers
# Expected: ("he", start=2), ("she", start=1), ("hers", start=2)
assert matches == [(0, 2), (1, 1), (3, 2)]

The two non-obvious bits:

1. The inner while in build() walks the failure chain rooted at v’s parent’s failure, looking for a defined transition on the new edge’s character. This is the source of the “amortized O(1) per node” claim — on average, this walk takes constant time across the whole BFS.
2. The dict_suffix chain in search() is what reports "he" when we end at state 5 spelling "she". Without it we’d miss every “shorter pattern is a suffix of a longer pattern” overlap.

A note on memory layout: storing goto as a list of dicts (one per node) is space-optimal (O(m) total transitions) but slow because of Python dict overhead. Production C/C++ implementations typically use a vector<int> of size 256 per node (for byte alphabets), trading a 256× memory blowup per node for cache-friendly array indexing. The trade is worth it: virus-scanner workloads see ~3–5× throughput gains from the dense-array representation despite the memory cost.

5. Complexity

5.1 Construction: O(m + m · |Σ|) or O(m) depending on transition representation

• Trie construction is O(m) regardless: each pattern character creates at most one node and one transition.
• Failure-link BFS: each node is visited once; the while f != 0 and ch not in goto[f] inner loop is amortized O(1) per node by the same potential-function argument as Knuth-Morris-Pratt (§5 of that note). Define Φ = depth of v for the current BFS node. Each f := failure[f] step strictly decreases Φ (failure links go from a node to a strictly shorter-string node). Each goto-edge we follow during BFS increases Φ by exactly 1. Total Φ-increments over the whole BFS is O(m) (one per trie edge), so total Φ-decrements (= total inner-while iterations) is O(m). Combined: failure-link construction is O(m) with hashed transitions.
• Building the full DFA (filling out every (state, char) → state transition) is O(m · |Σ|): you do |Σ| transitions per state, and there are m+1 states.

For typical interview discussion, quoting O(m) for construction with hashed transitions is correct and sufficient.

5.2 Search: O(n + z)

• The outer for loop runs n times.
• The inner while s != 0 and ch not in goto[s] is amortized O(1) per outer iteration by the exact same potential-function argument as KMP. Define Φ = depth of s (the current state). Each failure-link traversal decreases Φ by at least 1; each goto transition increases Φ by at most 1; we have n outer iterations, so total Φ increments ≤ n, so total decrements ≤ n. Total inner-while work across the entire search is O(n).
• The dict-suffix-link emission loop runs once per emitted match. So its total cost across the whole search is O(z).
• Sum: O(n + z).

If we don’t enumerate matches but only need a yes/no “did any pattern occur,” the bound becomes O(n) (we can short-circuit on the first accepting state).

5.3 Space

• Trie: O(m) nodes.
• Each node carries failure, dict_suffix, output. So total O(m) for the index data structures.
• For the dense-array DFA: O(m · |Σ|) — the standard memory cost in production scanners.

5.4 Comparison with naive multi-pattern matching

Running Knuth-Morris-Pratt independently for each of the k patterns costs O(k·n + m). For small k (a handful of patterns) the constant factor often makes that approach faster in wall-clock time despite the extra k factor. Aho-Corasick’s win is asymptotic and cache-locality: one pass over the text touches every relevant pattern, instead of k passes each missing the cache differently. For k in the thousands (virus signatures, web filters), Aho-Corasick is dramatically faster.

5.5 Streaming / online property

Like KMP, Aho-Corasick reads the text left-to-right and never rewinds. This means it can be run on a streaming input (a network socket, a memory-mapped file scanned in chunks) without buffering. Snort and Suricata both rely on this: they Aho-Corasick-match every packet’s payload against tens of thousands of signatures in a single pass, with no buffering beyond the packet boundary itself.

6. Variants and Extensions

6.1 Compressed/double-array trie

For very large pattern sets (millions of patterns), the trie’s memory dominates. The double-array trie representation (Aoe 1989) packs all transitions into two parallel integer arrays via a clever check/base scheme, achieving O(m) space with O(1) transition time. This is what darts-clone and marisa-trie ship; both have Aho-Corasick layers built atop them.

6.2 Output sets per node

In the trace above, each accepting node had exactly one pattern. In general, two distinct patterns can share an endpoint (e.g., if pattern set is {"abc", "abc"} — duplicates) or a node can be the endpoint of one pattern and the suffix-target of another (the dict-suffix mechanism merges these). The cleanest formulation stores output as a set of pattern indices at each node and does the dict-suffix walk to merge endpoints reachable via failure links.

6.3 Streaming with bounded memory

When the patterns are themselves streamed (e.g., a database of signatures that updates while scanning is happening), the dynamic Aho-Corasick problem arises. Existing literature handles incremental insert (Meyer’s online construction, related to suffix-tree online algorithms) but deletion remains an open practical problem; most production systems just rebuild the automaton periodically.

6.4 Generalized matching

By treating each “pattern” as a regex with limited operators (alternation, character classes), the Aho-Corasick framework extends to multi-regex matching. Hyperscan (Intel’s open-source pattern-matching library) is essentially Aho-Corasick over compiled regex fragments, with vectorized literal-prefix scanning.

6.5 Approximate matching

Plain Aho-Corasick is exact matching only. For approximate matching (k mismatches, k edits), the standard approach is to run Aho-Corasick on a modified automaton that accepts words within edit distance k — but the state space blows up exponentially in k. For k = 1, a doubled trie (with one “mismatch slot” per state) works; for larger k, it’s usually faster to use bit-parallel techniques (Wu-Manber).

6.6 Wu-Manber alternative

For multi-pattern matching where all patterns share a minimum length, Wu-Manber 1994 offers a Boyer-Moore-flavored alternative that skips ahead by hashing a window of characters. On typical workloads (short alphabets, moderate pattern counts) Wu-Manber beats Aho-Corasick by 2–5× wall-clock despite O(n) worst-case behavior. agrep uses Wu-Manber; grep -F uses Aho-Corasick (or, increasingly, Aho-Corasick with SIMD literal-prescan). The choice depends on average-case vs worst-case priorities.

7. Production / Real-World Use

• fgrep / grep -F (GNU coreutils) — -F mode reads the patterns and builds an Aho-Corasick automaton.
• Snort / Suricata (network IDS) — every signature’s literal prefix participates in an Aho-Corasick scan of every packet payload. The accepting-state hits trigger more expensive regex matching downstream.
• ClamAV — antivirus signatures (millions, mostly literal byte sequences) are matched via Aho-Corasick.
• fail2ban-style log scanners — match each log line against thousands of attack-pattern signatures.
• Plagiarism detection — Aho-Corasick on n-gram signatures from reference corpus; an incoming submission’s matches against many sources in one pass.
• Compiler frontends — keyword recognition is sometimes done with Aho-Corasick when keywords are large; for small keyword sets a hand-rolled DFA wins.
• DNA / protein motif scanning — match a database of motifs against a genome in linear time.

8. Pitfalls

8.1 Forgetting the dictionary-suffix-link

A trap many implementations fall into: they implement failure links correctly but only emit the pattern at the current state, forgetting that a pattern can end at an ancestor along the failure chain. The bug is invisible on patterns that don’t suffix-overlap (e.g., random strings) and catastrophic on dictionaries that do ("hers" and "he"). Always emit by walking the dict-suffix-link chain.

8.2 Self-loop on root for failure links

Children of root must have failure = root, not failure = self. The latter creates an infinite loop in the inner while in search. The pseudocode in §3.2’s first lines special-cases depth-1 nodes for exactly this reason.

8.3 Empty-pattern handling

If any pattern is the empty string "", the algorithm should report a match at every position 0..n. Most implementations either reject empty patterns at insert time or special-case them in the output-emission step. Failing to handle this leads to “match-at-every-position” floods.

8.4 Duplicate patterns

If "foo" is inserted twice, the user usually wants two reports per occurrence (in the order of pattern indices). Implementations that overwrite the output set on the second insert will silently report only one. Either de-duplicate on insert or store output as a multiset.

8.5 Confusing failure links with dict-suffix-links

They serve different purposes. Failure links are for transition (on a mismatch, where to go next). Dict-suffix-links are for output (at this state, what other patterns also end here?). Some references conflate them; CLRS-style presentations keep them separate, which is clearer to implement.

8.6 Alphabet-size assumption in complexity claims

Asserting “O(m + n + z)” implicitly assumes O(1) transition lookup, which requires hash-based or dense-array transitions. With sorted-list transitions per node (compact but slow), each lookup is O(log |Σ|) and the runtime gains a log |Σ| factor. For DNA alphabets (|Σ| = 4) the difference is a constant; for full Unicode it is not.

8.7 Online-construction temptation

Aho-Corasick’s BFS construction assumes you have all the patterns up front. There’s no clean way to insert a new pattern after build() has been called without rebuilding the failure links. Production virus scanners batch signature updates and rebuild the whole automaton; trying to maintain it incrementally is a research-grade problem.

9. Diagram — Trie with Failure Links

graph TD
    root((0:""))
    h((1:h))
    he((2:he))
    hi((6:hi))
    his((7:his))
    her((8:her))
    hers((9:hers))
    s((3:s))
    sh((4:sh))
    she((5:she))

    root -->|h| h
    root -->|s| s
    h -->|e| he
    h -->|i| hi
    he -->|r| her
    her -->|s| hers
    hi -->|s| his
    s -->|h| sh
    sh -->|e| she

    he -.fail.-> root
    hi -.fail.-> root
    his -.fail.-> s
    her -.fail.-> root
    hers -.fail.-> s
    sh -.fail.-> h
    she -.fail.-> he

What this diagram shows. Solid edges are the trie’s goto transitions, labelled by the character consumed. Dashed edges are failure links — they point from each node to the longest proper-suffix node in the trie. Pattern endpoints (he, she, his, hers) are the nodes whose strings are dictionary patterns. Two failure-link patterns are visible: (a) she → he is the most interesting — it points from one accepting state to another accepting state, which is why the dict-suffix-link mechanism (§3.2 final lines) is necessary to emit "he" whenever we visit "she". (b) his → s and hers → s show how unrelated patterns share fallback states once their unique prefixes have run out. Failure links never point to deeper nodes (they always shorten the current matched string), which is what guarantees the BFS construction terminates and the search amortized analysis works.

10. Common Interview Problems

LC# / Source	Problem	Use of Aho-Corasick
LC 1032	Stream of Characters	Reverse all dictionary words, build AC; on each new char, walk back through automaton. (Equivalent to AC on the reversed dictionary against a reversed-prefix stream.)
LC 30	Substring with Concatenation of All Words	Tokens-as-symbols variant; AC on the token alphabet works but is overkill — sliding window typically wins.
LC 745	Prefix and Suffix Search	Trie + suffix tricks; AC’s machinery overlaps but isn’t quite the right tool here.
LC 1408	String Matching in an Array	Naive O(n²) is fast enough; AC is overkill but correct.
Codeforces 86C	Genetic engineering	Forbidden-substring DP overlaid on the AC automaton — AC states become DP states. Classic.
Codeforces 696D	Legen…	DP on AC automaton + matrix exponentiation — count strings of length k that contain ≥ one of the patterns.
AtCoder ABC 268 Ex	Taboo	Minimum deletions to avoid any of n forbidden substrings — AC + greedy / DP on automaton states.

The pattern Aho-Corasick + DP on automaton states is the high-leverage interview / contest application: any “count / minimize / decide whether a string of length L contains some of these patterns” question can be solved in O((m + |Σ|·m)·L) by treating AC states as DP nodes.

11. Open Questions

• Does the dense-DFA representation always beat the failure-link representation on modern CPUs, or does the cache-blowup at high m hurt? Hyperscan’s authors argue for hybrid representations.
• What is the practical break-even for k (number of patterns) below which independent KMPs beat Aho-Corasick? Anecdotal: ~10 patterns. No rigorous benchmark I trust.
• Is there an online (incremental-pattern-insertion) Aho-Corasick variant with sub-O(m) update cost? Existing literature suggests O(√m) amortized per insert via periodic rebuilds, but I haven’t verified.

Resolved — both bounds are standard, alphabet-dependence is real. Wikipedia’s Aho–Corasick article gives the simple linear summary: “complexity of the algorithm is linear in the length of the strings plus the length of the searched text plus the number of output matches,” i.e. O(m + n + z) — without specifying the transition representation. The CP-Algorithms reference implementation makes the alphabet-size cost explicit: the dense-transition automaton stores k = |Σ| transitions per state, so its memory is O(m·k) and its BFS/recursive construction runs in O(m·k). Search itself is O(n + z) regardless of representation. The two phrasings reconcile cleanly: with hashed/sparse transitions and amortized-O(1) hashing, construction is O(m); with dense |Σ|-array transitions, it is O(m·|Σ|). Production virus scanners pay the O(m·|Σ|) construction cost once at startup to win cache-friendly O(1) table-lookup transitions during search. So both numbers in §5.1 are correct and refer to different transition encodings — there is no contradiction to flag.

12. See Also

• Knuth-Morris-Pratt — single-pattern ancestor; the failure-link concept generalizes to AC
• Trie — the underlying data structure
• Z-Algorithm — alternative single-pattern linear-time approach
• Rabin-Karp — randomized linear-time (multi-pattern via shared hash, but typically loses to AC for large k)
• Manacher’s Algorithm — KMP-family amortized analysis applied to palindromes
• String Hashing — orthogonal multi-pattern technique
• Big-O Notation — for the amortized argument
• SWE Interview Preparation MOC