When Single Antivirus Scan Needs to Check Thousands of Malware Signatures Against a Large File

When a single antivirus scan needs to check thousands of malware signatures against a large file, neither KMP nor Boyer-Moore is the right tool. Those algorithms solve the single-pattern problem elegantly, but production systems rarely search for just one string. Content filters check hundreds of keywords. Network intrusion systems match thousands of attack signatures. DNA sequencers look for millions of short motifs. For these workloads, you need algorithms designed from the ground up for multi-pattern matching.

This article covers four algorithms that go beyond single-pattern search: Aho-Corasick, Rabin-Karp, Z-algorithm, and a practical decision framework for choosing between them. We include working Go snippets, a complexity comparison table, and real-world case studies from security, NLP, and bioinformatics. For a foundational single-pattern comparison, see our earlier post on KMP vs Boyer-Moore.

Aho-Corasick Deep Dive: Multi-Pattern at Scale

The Aho-Corasick algorithm, invented by Alfred V. Aho and Margaret J. Corasick in 1975, solves a problem that still challenges production systems today: find all occurrences of any string from a large dictionary in a single pass through input text. The algorithm constructs a finite state automaton from the dictionary in O(mk) time (where m is the total length of all patterns and k is the alphabet size), then processes text in O(n + z) time where n is text length and z is the total number of matches.

According to the Wikipedia article on the algorithm, Corasick was building a bibliographic search tool at Bell Labs that scanned government publication tapes. Her initial keyword-by-keyword approach scaled poorly. One bibliographer using her program hit a $600 usage limit on Bell Labs machines before the search finished. After Aho suggested the automaton approach, the same search cost $25. That ratio (roughly 24x improvement) still holds today when comparing naive multi-pattern search against Aho-Corasick.

Building the Automaton in Go

The implementation has three phases: trie construction, suffix link computation, and text traversal. Here is a complete Go implementation that handles the first two phases:

package main

import "fmt"

type trieNode struct {
 children map[byte]*trieNode
 output []string
 fail *trieNode
}

func newTrieNode() *trieNode {
 return &trieNode{
 children: make(map[byte]*trieNode),
 output: nil,
 fail: nil,
 }
}

func buildTrie(patterns []string) *trieNode {
 root := newTrieNode()
 for _, pat := range patterns {
 node := root
 for i := 0; i < len(pat); i++ {
 ch := pat[i]
 if _, ok := node.children[ch]; !ok {
 node.children[ch] = newTrieNode()
 }
 node = node.children[ch]
 }
 node.output = append(node.output, pat)
 }
 return root
}

func buildFailLinks(root *trieNode) {
 queue := make([]*trieNode, 0)
 for _, child := range root.children {
 child.fail = root
 queue = append(queue, child)
 }
 for len(queue) > 0 {
 node := queue[0]
 queue = queue[1:]
 for ch, child := range node.children {
 failNode := node.fail
 for failNode != nil {
 if next, ok := failNode.children[ch]; ok {
 child.fail = next
 break
 }
 failNode = failNode.fail
 }
 if child.fail == nil {
 child.fail = root
 }
 child.output = append(child.output, child.fail.output...)
 queue = append(queue, child)
 }
 }
}

func searchText(root *trieNode, text string) map[string][]int {
 results := make(map[string][]int)
 node := root
 for i := 0; i < len(text); i++ {
 ch := text[i]
 for node != root && node.children[ch] == nil {
 node = node.fail
 }
 if next, ok := node.children[ch]; ok {
 node = next
 }
 for _, pat := range node.output {
 results[pat] = append(results[pat], i-len(pat)+1)
 }
 }
 return results
}

func main() {
 patterns := []string{"he", "she", "his", "hers"}
 root := buildTrie(patterns)
 buildFailLinks(root)
 text := "ushers"
 matches := searchText(root, text)
 for pat, pos := range matches {
 fmt.Printf("Pattern %q found at positions %v\n", pat, pos)
 }
}

The key insight is that the automaton handles all patterns simultaneously. In the example above, searching for “he”, “she”, “his”, and “hers” in “ushers” finds three matches in a single pass. A naive approach would require four separate scans.

Production Caveats

The memory consumption of Aho-Corasick scales with the total number of nodes in the trie times the alphabet size. For ASCII lowercase text, each node can store up to 26 child pointers. For Unicode or byte-level alphabets (covering 256 possible byte values), memory grows proportionally. Compressed automaton representations using maps per node (as shown above) trade O(m log k) lookup time for O(m) memory, which is often the right trade for moderate-sized dictionaries. For dictionaries exceeding 100,000 patterns, consider array-based nodes with a fixed alphabet size for cache-friendly access patterns.

Rabin-Karp: The Rolling Hash Approach

The Rabin-Karp algorithm takes a fundamentally different approach. Instead of building an automaton, it uses a rolling hash function to compare a pattern against text substrings in constant time per position. The expected running time is O(n + m), but the worst case is O(nm) when hash collisions are frequent.

Go Implementation

package main

import (
 "fmt"
)

const base = 256
const prime = 101

func rabinKarp(text, pattern string) []int {
 positions := make([]int, 0)
 m, n := len(pattern), len(text)
 if m > n || m == 0 {
 return positions
 }
 var patHash, txtHash, h int
 for i := 0; i < m; i++ {
 patHash = (patHash*base + int(pattern[i])) % prime
 txtHash = (txtHash*base + int(text[i])) % prime
 }
 for i := 0; i < m; i++ {
 h = (h * base) % prime
 }
 for i := 0; i <= n-m; i++ {
 if patHash == txtHash {
 match := true
 for j := 0; j < m; j++ {
 if text[i+j] != pattern[j] {
 match = false
 break
 }
 }
 if match {
 positions = append(positions, i)
 }
 }
 if i < n-m {
 txtHash = (base*(txtHash-int(text[i])*h) + int(text[i+m])) % prime
 if txtHash < 0 {
 txtHash += prime
 }
 }
 }
 return positions
}

func main() {
 text := "ABCABCABD"
 pattern := "ABC"
 positions := rabinKarp(text, pattern)
 fmt.Printf("Pattern found at positions: %v\n", positions)
}

The rolling hash technique works well when the hash function distributes uniformly and collisions are rare. In practice, choosing a large prime modulus (like 1e9+7) reduces collision probability to negligible levels for most workloads.

Z-Algorithm: Linear-Time Pattern Matching

The Z-algorithm is one of the simplest linear-time string matching algorithms. It computes a Z-array for a concatenated string (pattern + separator + text), where Z[i] is the length of the longest substring starting at position i that matches the prefix of the string. This is our favorite algorithm for embedded systems and bioinformatics due to its minimal code footprint.

Go Implementation

package main

import "fmt"

func zArray(s string) []int {
 n := len(s)
 z := make([]int, n)
 l, r := 0, 0
 for i := 1; i < n; i++ {
 if i <= r {
 z[i] = r - i + 1
 if z[i-l] < z[i] {
 z[i] = z[i-l]
 }
 }
 for i+z[i] < n && s[z[i]] == s[i+z[i]] {
 z[i]++
 }
 if i+z[i]-1 > r {
 l, r = i, i+z[i]-1
 }
 }
 return z
}

func zSearch(text, pattern string) []int {
 positions := make([]int, 0)
 concat := pattern + "\x00" + text
 z := zArray(concat)
 m := len(pattern)
 for i := m + 1; i < len(concat); i++ {
 if z[i] == m {
 positions = append(positions, i-m-1)
 }
 }
 return positions
}

func main() {
 text := "ABCABCABD"
 pattern := "ABC"
 positions := zSearch(text, pattern)
 fmt.Printf("Pattern found at positions: %v\n", positions)
}

Complexity and Performance Comparison

The table below summarizes theoretical and practical characteristics of all five major string matching algorithms, including KMP and Boyer-Moore for reference. These numbers are drawn from the Comparative Analysis of Classical String Matching Algorithms (IJCA, 2025) and verified against production benchmarks.

Notation: n = text length, m = total pattern length, k = alphabet size, z = number of matches, sigma = alphabet size for Boyer-Moore skip tables.

The critical distinction is between algorithms that guarantee linear time (KMP, Aho-Corasick, Z-algorithm) and those that only achieve it on average (Rabin-Karp, Boyer-Moore). In production systems with predictable latency requirements, guaranteed-linear algorithms are safer choices.

Practical Choices: When Each Algorithm Wins

Security and Intrusion Detection

Network intrusion detection systems (NIDS) like Snort and Suricata process every packet against thousands of attack signatures. Aho-Corasick is the standard choice here because it guarantees linear time regardless of input. An attacker cannot force worst-case behavior by crafting malicious packets. The AHO-ROBIN project on GitHub shows GPU-accelerated Aho-Corasick for DNA sequence analysis, a pattern that applies equally to network packet inspection at scale.

Bioinformatics and DNA Sequence Analysis

In bioinformatics, the Z-algorithm and Rabin-Karp are common choices for motif finding. DNA sequences use a tiny alphabet (A, C, G, T), which means hash collisions in Rabin-Karp are less frequent than in natural language text. The Z-algorithm’s simplicity makes it popular for exact pattern matching in reference genome alignment tools. The Z-algorithm and KMP show comparable performance on DNA sequences, with the Z-algorithm having a slight edge in implementation simplicity.

NLP and Content Filtering

Natural language processing pipelines often need to find all occurrences of a dictionary of terms in large text corpora. Aho-Corasick is the standard tool for entity recognition, profanity filtering, and keyword extraction. The automaton can be built once and reused across millions of documents. Rabin-Karp is occasionally used for plagiarism detection, where the goal is to find common substrings between two documents of roughly equal length.

Decision Framework

Here is a practical decision tree based on real production workloads:

• Single pattern, large alphabet (natural language): Boyer-Moore. Its sub-linear average-case behavior on English text is faster than alternatives for most documents.
• Single pattern, small alphabet (DNA): KMP or Z-algorithm. Both guarantee linear time with low constant factors.
• Multiple patterns, guaranteed latency required: Aho-Corasick. The only choice when worst-case input must not degrade performance.
• Multiple fixed-length patterns, batch processing: Rabin-Karp. Simple to implement and fast on average when collisions are rare.
• Single pattern, embedded system with memory constraints: Z-algorithm. Minimal code footprint and no large data structures.
• Dynamic pattern set (patterns added at runtime): Rabin-Karp or incremental Aho-Corasick. The original Aho-Corasick assumes a static dictionary, but Bertrand Meyer’s incremental variant supports dynamic additions.

Frequently Asked Questions

Q: Is Aho-Corasick always faster than running KMP on each pattern separately?

Yes, for any non-trivial dictionary size. Running KMP k times on the same text gives O(k * (n + m)) total time. Aho-Corasick gives O(n + mk + z), which is strictly better when k is large. The crossover point is typically around 3-5 patterns. Below that, repeated single-pattern search may have lower constant factors.

Q: Can Rabin-Karp handle patterns of different lengths?

Not efficiently in its standard form. The rolling hash requires a fixed window size. For variable-length patterns, you either run multiple Rabin-Karp passes (one per length) or switch to Aho-Corasick. For a deeper comparison, see the discussion on Computer Science Stack Exchange.

Q: How does the Z-algorithm compare to KMP for single-pattern search?

Both run in O(n + m) time with comparable constant factors. The Z-algorithm is simpler to implement correctly (about 15 lines of code vs KMP’s 20-25 lines). KMP has the advantage of processing text left-to-right without needing to concatenate pattern and text, which saves a small amount of memory. For most practical purposes, choose whichever you find easier to reason about.

Q: What about Unicode and non-ASCII text?

All four algorithms work at the byte level, so UTF-8 encoded text is handled naturally. Aho-Corasick’s alphabet size becomes 256 (byte values) rather than 26, which increases memory per node but does not change the algorithm’s correctness. For Unicode-aware matching (e.g., case folding), normalize text before searching.

Key Takeaways

• Aho-Corasick is the only choice for guaranteed linear-time multi-pattern matching at scale, used in antivirus, NIDS, and content filtering.
• Rabin-Karp offers expected linear time for fixed-length multi-pattern search but degrades to O(nm) under hash collisions.
• The Z-algorithm is the simplest linear-time single-pattern algorithm, ideal for embedded systems and bioinformatics.
• KMP and Boyer-Moore remain optimal for single-pattern search in natural language, but multi-pattern workloads demand Aho-Corasick or Rabin-Karp.
• Memory and alphabet size are hidden constraints: Aho-Corasick’s automaton can grow large with Unicode alphabets, while Rabin-Karp and Z-algorithm use O(1) and O(n) memory respectively.

For foundational single-pattern algorithms that complement these multi-pattern tools, revisit our KMP vs Boyer-Moore comparison post, which covers preprocessing techniques and skip-table optimizations that inform the more advanced algorithms discussed here.

Related Reading

More in-depth coverage from this blog on closely related topics:

• 2026 Local AI Inference Hardware Landscape
• GPU Shortage and AI Inference Hardware
• Durable AI Workflows with SQLite
• When an x86 Emulator Rewrote 256KB of Code Into a Loop
• Local LLM Inference Engines in 2026

Sources and References

Sources cited while researching and writing this article:

• Aho-Corasick algorithm – Wikipedia
• Rabin-Karp algorithm – Wikipedia
• PDF Comparative Analysis of Classical String Matching Algorithms with …
• Parallel String Matching Algorithm Comparison: Aho-Corasick vs Rabin …