Throughout this module, we've seen how Rabin-Karp achieves O(n + m) expected time for single-pattern matching—comparable to KMP, though without the same worst-case guarantee. So why choose Rabin-Karp?\n\nThe answer lies in its killer feature: the ability to efficiently search for multiple patterns simultaneously. While KMP would require separate passes for each pattern, Rabin-Karp can check k patterns at each position with minimal overhead, achieving O(n + km) expected time instead of O(kn + km).\n\nThis capability makes Rabin-Karp the algorithm of choice for many real-world applications: plagiarism detection, malware signature scanning, multi-keyword search, and bioinformatics sequence analysis.

Let's formalize the multi-pattern matching problem and understand why naive approaches are inefficient.\n\nProblem definition:\n\nGiven:\n- Text T of length n\n- Set of k patterns P₁, P₂, ..., Pₖ with total length M = Σ|Pᵢ|\n\nFind: All occurrences of any pattern in the text.\n\nNaive approach: Run single-pattern algorithm k times\n\n\nfor each pattern P in patterns:\n find_all_occurrences(text, P) // O(n + m) per pattern\n\n\nTotal time: O(k × n + M) = O(kn + M)\n\nFor 1000 patterns and a 1MB text, this means ~1 billion operations. Completely impractical.

The fundamental inefficiency:\n\nRunning separate searches means reading the text k times. If the text is large (e.g., a genome), this is extraordinarily wasteful.\n\n\nPattern 1: Scan entire text → O(n)\nPattern 2: Scan entire text → O(n)\n...\nPattern k: Scan entire text → O(n)\n─────────────────────────────────\nTotal: k × O(n) = O(kn)\n\n\nThe goal:\n\nCan we scan the text just once and check all patterns at each position? This would give O(n) text scanning plus O(k) work per position for pattern checking, totaling O(n × something-less-than-k) if we're clever.\n\nRabin-Karp achieves exactly this through hash-based filtering.

Rabin-Karp's multi-pattern matching uses a simple but powerful insight: store all pattern hashes in a set, then check if each window's hash is in the set.\n\nAlgorithm structure:\n\n1. Preprocessing:\n - Compute hash of each pattern Pᵢ\n - Store all hashes in a hash set (for O(1) lookup)\n - Note: assumes all patterns have the same length m\n\n2. Matching:\n - Compute initial window hash\n - For each position:\n - Check if window hash is in the pattern hash set (O(1))\n - If yes: verify which pattern(s) match\n - Roll the hash to next position\n\nWhy this works:\n\n\nPattern hashes: {H(P₁), H(P₂), ..., H(Pₖ)} // Stored in hash set\n\nAt each position i:\n window_hash = H(text[i:i+m])\n if window_hash in pattern_hashes: // O(1) lookup!\n verify and report matches\n\n\nThe key is that checking if a hash exists in a set takes O(1) average time, regardless of how many patterns we have!

The basic multi-pattern Rabin-Karp assumes all patterns have the same length. Real-world applications often require searching for patterns of varying lengths.\n\nChallenge:\n\nWith different pattern lengths, we need different window sizes. Rolling hashes for different window sizes don't share computation.\n\nSolutions:\n\nApproach 1: Group by length\n\nGroup patterns by length and run separate searches for each group:\n\n\npatterns_by_length = group_patterns(patterns)\nfor length, patterns_of_this_length in patterns_by_length:\n run_rabin_karp(text, patterns_of_this_length, window_size=length)\n\n\nComplexity: O(L × n) where L = number of distinct lengths\n\nThis is efficient when there are few distinct lengths.

Approach 2: Minimum-length filtering\n\nCompute hash for the minimum pattern length. Use this as a preliminary filter, then verify longer patterns:\n\n\nmin_length = min(len(p) for p in patterns)\npreliminary_hash = rolling_hash(text, min_length)\n\nfor each position where preliminary hash matches any pattern prefix:\n check all patterns whose prefix matched\n\n\nThis is more complex but reduces text scans to one.\n\nApproach 3: Use Aho-Corasick\n\nFor truly optimal variable-length multi-pattern matching, consider Aho-Corasick (briefly discussed later). It achieves O(n + M + z) where z = total match count.

Let's rigorously analyze the complexity of multi-pattern Rabin-Karp.\n\nParameters:\n- n = text length\n- k = number of patterns\n- m = pattern length (assuming equal lengths)\n- M = total pattern length = k × m\n\nPreprocessing:\n\n\nfor each of k patterns: // k iterations\n compute hash: // O(m) each\n add to hash set: // O(1) expected\n\n\nTotal preprocessing: O(km) = O(M)\n\nMatching:\n\n\nfor each of n-m+1 positions: // O(n) iterations\n hash lookup in set: // O(1) expected\n if match: verify // O(?) - see below\n roll hash: // O(1)\n\n\nBase matching: O(n) (without considering verification)

Verification analysis:\n\nVerification occurs when window hash is found in pattern hash set. This happens for:\n1. Actual matches (we want these)\n2. Hash collisions (spurious hits)\n\nExpected spurious hits:\n\nWith k patterns and modulus q:\n\nP(window hash matches any pattern hash) ≤ k/q\n\n\nFor n-m+1 windows:\n\nE[spurious hits] ≤ (n-m+1) × k/q ≈ nk/q\n\n\nWith q = 10^9, n = 10^6, k = 100:\n\nE[spurious hits] ≈ 10^6 × 100 / 10^9 = 0.1\n\n\nNegligible spurious hits expected!\n\nTotal expected time:\n\n\nPreprocessing + Matching + Verification\n= O(M) + O(n) + O(A × m)\n= O(n + M + Am)\n\n\nWhere A = actual match count. For typical scenarios with few matches: O(n + M)

Multi-pattern Rabin-Karp powers numerous real-world systems. Let's explore the key applications in depth.\n\nApplication 1: Plagiarism Detection\n\nProblem: Given a document and a corpus of existing documents, find copied passages.\n\nApproach:\n- Extract n-grams (e.g., 5-word phrases) from the target document\n- Search for each n-gram in corpus documents\n- High density of matches indicates plagiarism\n\npython\n# Pseudo-code for plagiarism detection\ngrams = extract_ngrams(target_document, n=5)\nfor corpus_doc in corpus:\n matches = rabin_karp_multi(corpus_doc, grams)\n if len(matches) / len(corpus_doc) > threshold:\n flag_as_plagiarism(target_document, corpus_doc, matches)\n\n\nRabin-Karp makes this feasible for large corpora.

Application 2: Malware Signature Scanning\n\nProblem: Scan files for known malware byte sequences (signatures).\n\nChallenges:\n- Thousands of signatures to check\n- Files can be gigabytes in size\n- Must be fast for real-time scanning\n\nSolution:\n- Store all signature hashes in a set\n- Stream file through rolling hash\n- O(file_size) regardless of signature count\n\nApplication 3: Intrusion Detection Systems (IDS)\n\nNetwork traffic is scanned for attack patterns:\n- SQL injection patterns\n- Cross-site scripting (XSS) markers\n- Known exploit payloads\n\nRabin-Karp enables line-rate scanning of network packets against thousands of attack signatures.\n\nApplication 4: DNA Sequence Analysis\n\nBioinformatics applications:\n- Find all occurrences of known gene sequences\n- Identify transcription factor binding sites\n- Search for primer sequences in genomes

For production systems handling millions of patterns or gigabytes of text, additional optimizations become important.\n\nOptimization 1: Bloom filter pre-screening\n\nInstead of a hash set, use a Bloom filter for pattern hashes:\n- Space: O(k) bits instead of O(k) hash entries\n- Lookup: Still O(1), often faster due to cache\n- Trade-off: Small false positive rate (acceptable with verification)\n\n\nbloom = BloomFilter(size=1000000, hash_count=7)\nfor pattern in patterns:\n bloom.add(hash(pattern))\n\n# During matching\nif bloom.might_contain(window_hash): # Fast!\n if window_hash in exact_hash_set: # Rare\n verify()\n\n\nOptimization 2: SIMD-accelerated hashing\n\nModern CPUs can compute multiple hashes in parallel using SIMD instructions:\n- Process 4-8 positions simultaneously\n- Vectorized modular arithmetic\n- 4-8× speedup on compatible hardware

Optimization 3: Pattern hash precomputation\n\nFor static pattern sets (e.g., malware signatures), precompute and cache:\n- Pattern hashes\n- Sorted hash array for binary search (if hash set overhead is too high)\n- Perfect hash function (zero collisions within pattern set)\n\nOptimization 4: Chunked processing for large texts\n\n\nfor chunk in text.chunks(CHUNK_SIZE):\n matches_in_chunk = rabin_karp(chunk, patterns)\n adjust_positions(matches_in_chunk, chunk.offset)\n yield matches_in_chunk\n\n\nBenefits:\n- Better cache utilization\n- Enables parallel processing of chunks\n- Reduces memory pressure for huge texts\n\nOptimization 5: Early termination\n\nFor some applications, we don't need all matches:\n- 'Find first' returns after single match\n- 'Find up to N' stops after N matches\n- 'Existence check' returns boolean on first match

Rabin-Karp isn't the only multi-pattern algorithm. The Aho-Corasick algorithm is a specialized automaton-based approach that guarantees optimal time complexity.\n\nAho-Corasick overview:\n\n- Builds a finite automaton (trie + failure links) from all patterns\n- Processes text in a single pass, following automaton transitions\n- Reports matches as automaton reaches accepting states\n\nComplexity comparison:

Where z = number of matches reported\n\nWhen to choose Rabin-Karp:\n\n1. Implementation simplicity is valued — Rabin-Karp is straightforward to implement correctly\n2. Patterns change frequently — No complex automaton to rebuild\n3. Patterns are equal length — Eliminates main limitation\n4. Expected case is sufficient — Worst case is astronomically rare\n\nWhen to choose Aho-Corasick:\n\n1. Guaranteed linear time is required — Security-critical, real-time systems\n2. Variable-length patterns naturally — No grouping needed\n3. Patterns are static — Automaton built once, used many times\n4. Many overlapping matches — Aho-Corasick handles naturally\n\nPractical guidance:\n\nFor most applications, either algorithm works well. Rabin-Karp's simplicity makes it a good default choice. Consider Aho-Corasick for specialized use cases like intrusion detection or antivirus where worst-case guarantees matter.

Let's build a complete, production-ready multi-pattern Rabin-Karp implementation that handles edge cases and provides useful features.

We've explored Rabin-Karp's killer feature in depth. Let's consolidate the key insights:

Module complete:\n\nYou've now mastered the Rabin-Karp algorithm comprehensively:\n\n1. Hashing for pattern matching — The conceptual foundation\n2. Rolling hash technique — O(1) hash updates\n3. Collision handling — Verification and mitigation strategies\n4. Complexity analysis — Expected O(n+m), worst O(nm)\n5. Multi-pattern advantage — The killer feature\n\nRabin-Karp is a beautiful example of how a simple idea (fingerprinting) combined with clever mathematics (rolling hash) produces a practical, powerful algorithm. Its multi-pattern capability makes it irreplaceable in many real-world systems.