How Aho-Corasick Multi-Pattern Search Works: Step-by-Step

1. Introduction and Core Concepts

Aho-Corasick multi-pattern search is a classic string matching algorithm that solves a fundamental problem in computer science: finding all occurrences of a large set of keywords simultaneously within a body of text. While traditional string search algorithms like Knuth-Morris-Pratt or Boyer-Moore are optimized for finding a single pattern, they become inefficient when you need to search for thousands or even millions of patterns at once. Running a single-pattern algorithm repeatedly for each keyword leads to prohibitive costs. The Aho-Corasick algorithm, invented by Alfred V. Aho and Margaret J. Corasick in 1975 at Bell Labs, eliminates this inefficiency by processing the text in a single pass, regardless of how many patterns you are searching for.

At its heart, the algorithm is a beautiful synthesis of three well-understood concepts: a trie, an automaton, and failure links inspired by the Knuth-Morris-Pratt algorithm. First, all patterns are inserted into a trie, which is a tree-like data structure where each edge represents a character and each path from the root represents a prefix of one or more patterns. This trie forms the skeleton of a deterministic finite automaton. The critical innovation is the addition of failure links, also called suffix links or fallback links. These links allow the automaton to efficiently transition to the next valid state when a character mismatch occurs, without ever needing to backtrack in the input text. This property makes the algorithm linear in the size of the input text plus the number of matches.

Understanding aho-corasick multi-pattern search matters because it underpins many of the high-performance systems we rely on daily. From intrusion detection systems that must scan network traffic for thousands of virus signatures in real time, to content filtering, plagiarism detection, bioinformatics for DNA sequence matching, and even the profanity filters in online games, the ability to match many patterns at line speed is essential. Its guarantee of linear time performance makes it a cornerstone of string algorithms and a frequent topic in advanced algorithms courses and technical interviews. Mastering it provides deep insight into how automata theory can be applied to solve practical engineering problems with optimal efficiency.

Core Terminology

To understand the algorithm, you must be familiar with several key terms. The trie is the prefix tree containing all patterns. Each node corresponds to a prefix of some pattern. The goto function defines the trie edges: where to go when the next character matches a child. The failure function defines where to go when there is no matching child; it points to the longest proper suffix of the current node's string that is also a prefix of some pattern in the trie. Finally, the output function at each node stores the set of patterns that end at that node or at any node reachable by following failure links, ensuring that all patterns that are suffixes of the current matched path are reported.

Why Not Just Use Multiple Searches?

A naive approach to multi-pattern search is to run a single-pattern search like Python's in operator or KMP for each pattern independently. If you have k patterns of average length m and a text of length n, this costs O(k * n * m) in the worst case, or O(k * (n + m)) with an optimized single-pattern algorithm. When k is large, for example 100,000 keywords in a spam filter, this becomes infeasible. Aho-Corasick reduces this to O(n + m_total + z), where m_total is the total length of all patterns and z is the number of matches. The text is scanned exactly once, character by character, and each character causes at most a constant number of state transitions. This decoupling of search time from the number of patterns is the algorithm's defining advantage.

2. How It Works

The aho-corasick multi-pattern search operates in two distinct phases: a preprocessing phase that builds the automaton from the set of patterns, and a searching phase that runs the automaton over the text. The preprocessing phase itself consists of two steps: building the trie and then augmenting it with failure and output links using a breadth-first search.

Phase one begins with an empty root node. Each pattern is inserted character by character. If a path for a prefix already exists, it is reused; otherwise, new nodes are created. Each node stores a dictionary of children, a failure pointer, and a list of pattern identifiers that terminate at that node. After all patterns are inserted, the resulting trie can already be used to search for patterns, but only by following exact matches from the root. It cannot handle mismatches efficiently.

The second part of preprocessing is what gives the algorithm its power. We compute the failure link for every node using a breadth-first traversal starting from the root's children. The failure link for the root is set to null or to itself, and its immediate children have their failure links set to the root. For any deeper node representing string s + c, where s is the string for its parent and c is the character on the edge to the node, its failure link is found by following the parent's failure link until we find a node that has a child on character c, or we reach the root. This is precisely analogous to the prefix function in KMP but generalized to a tree. During this BFS, we also propagate outputs: if the failure node of a node is the end of a pattern, then the current node should also output that pattern, because that pattern is a suffix of the current path. This ensures we do not miss patterns that are suffixes of other patterns, such as finding both "he" and "she" when scanning "she".

The Automaton in Action

Once the automaton is built, searching is remarkably simple and efficient. We maintain a current state, initially the root. For each character in the text, we attempt to follow a goto edge from the current state. If such an edge exists, we take it. If not, we follow failure links repeatedly until we either find a state that has the desired edge or we return to the root. Once we transition to the next state, we report all patterns in that state's output list. The current position in the text minus the pattern length gives the start index of each match. Because we never move backwards in the text and each character causes at most a few failure traversals, the search is linear.

Crucially, the failure links guarantee that we never miss a potential match that starts in the middle of a previous partial match. For example, with patterns "ab", "bc", and "abc", and text "abc", after matching "ab", the next character "c" would cause a mismatch if we restarted from the root. The failure links allow the automaton to realize that the suffix "b" of "ab" is a prefix of "bc" and "abc", and transition accordingly without re-examining characters. This automaton is deterministic and complete after construction, meaning every character from any state has a defined transition, either via a goto edge or a chain of failure links.

Visualizing the Structure

Consider patterns "he", "she", "his", and "hers". The trie has a root with children 'h' and 's'. The 'h' branch continues to 'e' and 'i', and so on. The failure link for the node representing "she" after 'h' points to the node for "he" after 'h', because "he" is the longest proper suffix of "she" that is also a trie prefix. Similarly, the node for "hers" will have a failure link that may point to another node. This interconnected structure transforms a simple tree into a powerful automaton with cross edges that capture all suffix-prefix relationships among the patterns.

3. Implementation

Implementing aho-corasick multi-pattern search in Python is an excellent exercise in data structure design. The implementation below is modular, well-commented, and suitable for production use with minor optimizations. We define a node class, functions to build the trie, build failure links, and search. This separation makes the logic clear and testable.

class TrieNode:
    def __init__(self):
        # Children maps character -> TrieNode
        self.children = {}
        # Failure link points to longest proper suffix that is a trie prefix
        self.fail = None
        # Output stores pattern ids that end at this node
        self.output = []
        # Optional flag for debugging
        self.is_end = False
        # For visualization, store character leading to this node
        self.char = None

def build_trie(patterns):
    """Build trie from list of patterns. Returns root node."""
    root = TrieNode()
    for pattern_id, pattern in enumerate(patterns):
        # Skip empty patterns
        if len(pattern) == 0:
            continue
        node = root
        for char in pattern:
            if char not in node.children:
                new_node = TrieNode()
                new_node.char = char
                node.children[char] = new_node
            node = node.children[char]
        node.is_end = True
        node.output.append(pattern_id)
    return root

from collections import deque

def build_failure_links(root):
    """Augment trie with failure links using BFS. Must be called after build_trie."""
    queue = deque()
    # Initialize depth 1 nodes: fail points to root
    for char, child in root.children.items():
        child.fail = root
        queue.append(child)
    
    # Root's fail is None to terminate while loops
    root.fail = None

    while queue:
        current = queue.popleft()
        for char, child in current.children.items():
            queue.append(child)
            # Find failure for child
            fail_node = current.fail
            while fail_node is not None and char not in fail_node.children:
                fail_node = fail_node.fail
            if fail_node is None:
                child.fail = root
            else:
                child.fail = fail_node.children[char]
            # Merge outputs: if fail node is terminal, child also outputs it
            # This handles suffix patterns like "he" inside "she"
            if child.fail.output:
                child.output.extend(child.fail.output)

def aho_corasick_search(text, root, patterns):
    """Search text for all patterns. Returns list of (pattern, start_index)."""
    results = []
    node = root
    for i, char in enumerate(text):
        # Follow failure links until we find a valid transition or hit root
        while node is not None and char not in node.children:
            node = node.fail
        if node is None:
            node = root
            continue
        # Take the goto transition
        node = node.children[char]
        # Report all patterns ending here
        for pattern_id in node.output:
            pattern = patterns[pattern_id]
            # Ensure pattern length > 0 to avoid division issues
            if len(pattern) > 0:
                start_index = i - len(pattern) + 1
                # Additional check: start_index >= 0 and < len(text)
                if start_index >= 0 and start_index < len(text):
                    results.append((pattern, start_index))
    return results

# Example usage
if __name__ == "__main__":
    patterns = ["he", "she", "his", "hers"]
    text = "ushers"
    root = build_trie(patterns)
    build_failure_links(root)
    matches = aho_corasick_search(text, root, patterns)
    print(matches)  # Expected: [('she', 1), ('he', 2), ('hers', 2)]

This implementation uses dictionaries for children, which is efficient for sparse alphabets and Python strings. For large alphabets or performance-critical code, an array of size alphabet or a double-array trie may be faster. Note the careful handling of None for the root's failure link and the propagation of outputs during BFS. An alternative optimization is to build a complete deterministic automaton by filling in missing goto transitions during BFS, which makes search O(n) with no while loop, at the cost of higher memory.

4. Step-by-Step Example

Let us walk through a concrete example to solidify understanding. We will use the classic pattern set P = {"he", "she", "his", "hers"} and text T = "ushers". This example is chosen because it contains overlapping patterns and suffix relationships that demonstrate why failure links are necessary.

Step 1: Build the Trie. We insert each pattern. The root has two children: 'h' and 's'. Path "he": root -> h -> e (node A, output ["he"]). Path "she": root -> s -> h -> e (node B, output ["she"]). Note that the 'h' after 's' is a different node than the root's 'h' child. Path "his": root -> h -> i -> s (node C, output ["his"]). Path "hers": root -> h -> e -> r -> s (node D, output ["hers"]). The trie now has 9 nodes plus root.

Step 2: Build Failure Links via BFS. Queue initially contains nodes for 'h' and 's' (depth 1), both fail to root. Next, we process node 'h' (root's child). Its children are 'e' and 'i'. For child 'e' (path "he"), we look at its parent's fail (root). Root has no child 'e', so fail goes to root. For child 'i' (path "hi"), similarly fail goes to root. Next, process node 's' (root's child). Its child is 'h' (path "sh"). Parent's fail is root, root has child 'h', so this node's fail points to root's 'h' node. This is the crucial link: "sh" suffix "h" is a prefix. Next, process node 'e' ("he"). Its child 'r' ("her"): parent fail is root, root has no 'r', so fail to root. Process node 'i' ("hi"): child 's' ("his"): parent fail is root, root has child 's', so fail to root's 's' node. Process node 'h' ("sh"): child 'e' ("she"): parent is root's 'h' node, which has child 'e', so fail points to node A ("he"). Thus node B's output becomes ["she", "he"] after merging. Finally, process "her" node 'r': child 's' ("hers"): parent fail is root, root has 's', so fail to root's 's'. Outputs are merged accordingly.

Step 3: Search Text "ushers". We iterate character by character with current state at root.

• i=0, char='u': root has no 'u' child, stay at root, no output.
• i=1, char='s': root has 's', move to node 's' (path "s"), no output.
• i=2, char='h': node 's' has child 'h', move to node "sh", no output yet.
• i=3, char='e': node "sh" has child 'e', move to node "she", output ["she", "he"]. We report "she" at 1 (3-3+1) and "he" at 2 (3-2+1). Both are correct; "he" is inside "she".
• i=4, char='r': node "she" has no 'r' child, follow fail to node "he". Node "he" has child 'r', so move to node "her", no output.
• i=5, char='s': node "her" has child 's', move to node "hers", output ["hers"]. Report "hers" at 2 (5-4+1).

Result: three matches found in a single pass. Without failure links, after matching "she", we would have missed "he" as a suffix, and after "she", the 'r' would have caused a restart and missed "hers". The failure links elegantly handle these transitions.

Tracing Failure Transitions

Notice at i=4, the transition from "she" on 'r' required one failure hop. In the worst case, a character may cause multiple hops, but amortized analysis shows each character is processed in constant time because each failure hop strictly decreases the depth of the current node, and depth can only increase by one per character via a goto edge. This ensures linear time overall.

5. Complexity Analysis

The efficiency of aho-corasick multi-pattern search is its primary selling point, but understanding its precise complexity in best, average, and worst cases is essential for system design and capacity planning. The analysis is split between preprocessing and searching.

Preprocessing time is dominated by building the trie and building failure links. Building the trie takes O(m_total) where m_total is the sum of lengths of all patterns, because each character of each pattern is inserted once. Building failure links takes O(m_total * alphabet) in the naive implementation with dictionary lookups, but with BFS it is O(m_total) assuming constant-time child lookups, as each node is processed once and each failure traversal is amortized. Space for the automaton is O(m_total * alphabet) in the worst case for a dense transition table, but O(m_total) nodes with dictionary children in practice. Each node stores at most one failure pointer and a list of outputs.

Searching time is O(n + z) where n is the text length and z is the total number of pattern occurrences reported. The n term comes from scanning each character once, and the z term accounts for output reporting. If many patterns match at the same position, for example patterns "a", "aa", "aaa" in text "aaaa", z can be large, up to O(n * sqrt(m_total)) in pathological cases, but typically z is small. Without output propagation optimization, worst-case search could be O(n * m_max) if we naively traverse failure chains to collect outputs at each step. By merging outputs during BFS, we ensure each match is reported in O(1) amortized time.

Space complexity during search is O(1) auxiliary besides the automaton and output list. The automaton itself is the dominant memory cost. For very large pattern sets, such as millions of keywords, memory can become a bottleneck, requiring compressed representations like double-array tries or succinct data structures.

In practice, the algorithm performs close to best case for natural language text and moderate pattern sets. The linear guarantee holds even for adversarial inputs, unlike Boyer-Moore which can degrade. The only non-linear factor is z, the number of matches, which is unavoidable since you must report each match. If you only need to know whether any pattern matches, you can stop early and achieve pure O(n + m_total).

6. Variations and Optimizations

While the classic Aho-Corasick is already optimal in asymptotic terms, numerous variations and optimizations exist to adapt it to specific constraints such as memory, alphabet size, and dynamic pattern sets. Understanding these helps you choose the right implementation for your use case.

One major optimization is the construction of a complete deterministic automaton, often called the goto-complete or DFA version. In the standard version, search follows failure links on mismatch via a while loop. In the optimized version, during BFS we fill in missing transitions for every node and every alphabet character, so that every state has a defined transition for every character. This makes search a simple loop with a single array lookup per character: state = go[state][char], with no while loop. This is significantly faster in tight loops, especially in C or hardware implementations, at the cost of O(nodes * alphabet) memory, which is prohibitive for large alphabets like Unicode. For ASCII or DNA alphabets (4 letters), it is ideal.

Another important variant handles dynamic pattern sets. The classic algorithm assumes patterns are static. If patterns are added or removed frequently, rebuilding the entire automaton is expensive. Research has produced dynamic Aho-Corasick structures using techniques like splitting patterns into groups and rebuilding incrementally, or using a failure-less variant with bit-parallelism. For many applications, a simpler approach of batch rebuilding periodically is sufficient.

Memory optimizations are critical for large-scale deployments. The Double-Array Trie compresses the trie into two integer arrays (base and check), drastically reducing memory and improving cache locality. The Compressed Aho-Corasick uses succinct data structures or replaces dictionary children with sorted arrays and binary search when node degree is low. For patterns with common suffixes, adding output links instead of merging outputs can save memory: instead of copying outputs, each node stores a pointer to the next output node in its failure chain, and search iterates through this chain to report matches.

Handling Large Alphabets and Case Sensitivity

For Unicode text, storing transitions for all possible characters is impossible. Implementations typically use hash maps or balanced trees for children, and failure traversal remains dictionary-based. Case-insensitive search can be handled by normalizing patterns and text to lower case during insertion and search, or by adding both cases to the trie. For wildcard or approximate matching, Aho-Corasick can be extended with additional automaton layers, but this quickly increases complexity and may be better served by other algorithms like Wu-Manber.

Parallel and Hardware Implementations

Modern high-throughput systems implement Aho-Corasick on GPUs, FPGAs, and multi-core CPUs. The text can be split into chunks and searched in parallel, though care must be taken to handle matches that cross chunk boundaries by overlapping chunks by max pattern length. Bit-parallel and SIMD implementations pack multiple characters or states into vector registers for faster scanning. These optimizations are common in network intrusion detection systems like Snort and Suricata, which must scan gigabits per second.

7. Real-World Applications

The theoretical elegance of aho-corasick multi-pattern search translates directly into practical impact across diverse domains. Its ability to scan once for many patterns makes it indispensable where throughput and latency are critical.

In cybersecurity, it is the workhorse of signature-based detection. Network intrusion detection systems (NIDS) like Snort, Suricata, and Bro/Zeek maintain databases of tens of thousands of attack signatures, virus definitions, and malicious URL patterns. Every packet payload must be scanned against all signatures at line speed. Aho-Corasick allows these systems to achieve multi-gigabit throughput without per-signature scanning. Similarly, antivirus engines scan files for malware signatures, and web application firewalls filter HTTP requests for SQL injection or XSS payloads.

In bioinformatics, researchers search DNA or protein sequences for many known motifs, primers, or gene markers. A genome may be billions of base pairs long, and the pattern set may contain thousands of short sequences. Aho-Corasick's linear scan is ideal for finding all occurrences of these motifs, for example locating all occurrences of a set of transcription factor binding sites in a genome. Tools like BLAST use related automata concepts for seeding alignments.

In information retrieval and natural language processing, the algorithm powers content filtering, keyword extraction, and entity recognition. Search engines use it to highlight query terms in documents, ad systems match large dictionaries of keywords against web pages for contextual advertising, and chat moderation systems filter profanity or sensitive information from user-generated content. Plagiarism detection services scan documents against large corpora of source phrases.

Other notable uses include data loss prevention systems that scan outgoing traffic for confidential patterns like credit card numbers or social security numbers, log analysis platforms that search for many error codes simultaneously, and even in compilers and text editors for multi-keyword syntax highlighting.

8. Comparison with Alternatives

Choosing the right multi-pattern search algorithm depends on pattern count, text length, alphabet size, and whether you need exact or approximate matching. Aho-Corasick is optimal for exact matching of many patterns, but alternatives may be simpler or faster for specific scenarios.

The naive approach of running a single-pattern algorithm like KMP or Python's efficient substring search for each pattern is easy to implement and benefits from highly optimized library code. However, its cost scales linearly with the number of patterns, making it unsuitable beyond a few dozen patterns. Regular expression engines can handle multiple patterns via alternation (pattern1|pattern2|...), but they typically compile to backtracking or NFA simulation that can exhibit exponential worst-case behavior and lack guarantees. Rabin-Karp can be extended to multiple patterns by hashing patterns and text windows, which is good for average-case performance but suffers from hash collisions and worst-case O(n*m) behavior.

Other dedicated multi-pattern algorithms include Commentz-Walter, which combines Boyer-Moore's bad-character heuristic with a trie and can be faster than Aho-Corasick on average for large alphabets and long patterns because it can skip characters. Wu-Manber is a block-based algorithm that hashes text blocks and is often faster in practice for natural language with moderate pattern sets, and is used in tools like agrep. For a small number of patterns, a well-tuned single-pattern algorithm may still win due to lower constant factors and preprocessing overhead.

In summary, if you need exact matching of a large, static set of patterns with guaranteed performance, Aho-Corasick is the gold standard. If you have only a handful of patterns, the overhead of building the automaton may not be worthwhile. If you need approximate matching, wildcards, or skipping, consider Wu-Manber or Commentz-Walter. For complex pattern languages, a regex engine built on automata theory may be more expressive, though often slower.

9. Common Mistakes and Best Practices

Implementing aho-corasick multi-pattern search correctly requires attention to subtle details that are easy to overlook. These pitfalls can lead to missed matches, incorrect positions, or performance degradation.

A frequent mistake is failing to propagate outputs through failure links. Beginners often only report patterns that end exactly at the current node, missing patterns that are suffixes of the matched path. For example, with patterns "he" and "she", matching "she" should report both. The fix is to merge the failure node's output into the child's output during BFS, or to traverse the output chain during search. Forgetting this leads to silent false negatives that are hard to debug.

Another common error is incorrect failure link construction order. Failure links must be built in breadth-first order, not depth-first, because a node's failure link depends on its parent's failure link already being computed. Using DFS or arbitrary order results in incorrect links and missed transitions. Always use a queue and process nodes level by level.

Handling empty patterns, duplicate patterns, and overlapping matches also causes bugs. Empty patterns should be ignored or handled explicitly, as they match at every position. Duplicate patterns should be stored with separate IDs or counts, otherwise you may under-report. When reporting matches, ensure you compute start indices correctly as i - len(pattern) + 1 and consider whether you want to report overlapping matches separately or coalesce them.

Performance pitfalls include using inefficient data structures for children. Using a Python dict is fine for most cases, but for very large automata, the overhead of dicts can be high. Consider using arrays for small alphabets or defaultdict optimizations. Also, building a complete DFA with all transitions precomputed can speed up search but may explode memory for Unicode. Profile your workload: if text is short and patterns are many, preprocessing cost dominates, so consider lazy construction or caching the automaton.

Best Practices

• Normalize text and patterns consistently for case-insensitive search before building the trie, rather than handling case during search.
• Store pattern strings separately and keep only IDs in nodes to save memory when patterns share suffixes.
• For streaming input, maintain automaton state across chunks and handle chunk boundaries by carrying over the last max_pattern_length - 1 characters.
• Add comprehensive tests with overlapping patterns, suffix patterns, and patterns that are prefixes of others.
• If you only need existence (any match), add early exit to avoid collecting all outputs and reduce z cost.
• Consider using established libraries like pyahocorasick for production, which are implemented in C and highly optimized, rather than pure Python for large-scale use.

10. Interview Questions

Aho-Corasick multi-pattern search is a favorite in senior software engineering and algorithms interviews because it tests understanding of tries, automata, BFS, and complexity analysis. Below are common questions and how to approach them.

Q1: How does Aho-Corasick achieve linear time regardless of the number of patterns? Explain the role of failure links.

Answer: The algorithm builds a trie of all patterns in O(m_total) and then augments it with failure links that point from each node to the longest proper suffix that is also a trie prefix. During search, we scan the text once, maintaining a current automaton state. For each character, we follow goto edges if possible, otherwise we follow failure links until a valid transition is found. Each character causes at most one goto advancement and a bounded number of failure hops amortized, because each failure hop reduces depth. Thus total transitions are O(n). Reporting matches adds O(z). The number of patterns k does not appear in the search complexity because the automaton encodes all patterns simultaneously; the text is not re-scanned per pattern.

Q2: Walk through building failure links for patterns ["a", "ab", "bab", "bc", "bca", "c", "caa"]. What is the failure link for the node representing "bca"?

Answer: Build trie, then BFS. Root children 'a','b','c' fail to root. For node "bca" (path b->c->a), its parent is "bc" (node for "bc"). Parent's fail: "bc" node's fail points to "c" node because "c" is longest suffix of "bc" that is a prefix. Now for child 'a' of "bc", we look at fail("bc") = "c" node, which has child 'a' ("ca"), so fail("bca") points to node "ca" (or more precisely the node for "ca" if "ca" is a prefix; if not, continue). In this set, "ca" is prefix of "caa", so fail points to node "ca". Its output would include patterns ending at "ca" if any, plus transitive outputs. This demonstrates suffix-prefix reasoning.

Q3: How would you modify Aho-Corasick to handle wildcard patterns like "he?lo" where ? matches any single character?

Answer: Classic Aho-Corasick does not support wildcards directly. Options: expand wildcards into all possible characters during trie building, which explodes pattern count; or modify automaton to have epsilon transitions or wildcard edges that match any character, similar to Thompson NFA. A more practical approach is to split patterns on wildcards into fragments and use Aho-Corasick to find fragments, then verify gaps. Alternatively, use a different algorithm like Wu-Manber or regex engines that natively support wildcards. For single-character wildcards, you could add a special child that is taken when no exact child matches, but this complicates failure links and may break determinism.

Q4: What is the space complexity and how would you reduce memory for 10 million patterns?

Answer: Space is O(m_total) nodes, each with children dict, fail pointer, output list. For 10 million patterns, this could be gigabytes. Reductions: use double-array trie to compress to two integer arrays, use succinct trie representations, store children in sorted arrays with binary search for low-degree nodes, share suffixes via DAG minimization, or use disk-backed or distributed automaton. Also, filter patterns: remove redundant patterns that are substrings of others if only longest match needed, or partition patterns by frequency and use two-level filtering. For many applications, an on-disk or memory-mapped automaton with caching is used.

Q5: Compare Aho-Corasick with building a hash set of patterns and checking every substring of the text.

Answer: Checking every substring would be O(n * max_len) substrings, each hash lookup O(max_len) to compute hash, leading to O(n * max_len) time and potentially O(n * max_len) hash computations, which is far worse than O(n + z). Even with rolling hash, you still check O(n) positions per pattern length, and you need to handle multiple lengths. Aho-Corasick is more efficient because it reuses prefix sharing and avoids re-hashing, and it naturally handles patterns of varying lengths without separate loops. Hash approach also suffers from collisions and does not easily report overlapping matches with positions without extra work.