Rabin-Karp String Matching with Rolling Hash

---

The Problem: Finding a Pattern in Text

Given a text string of length n and a pattern of length m, find all occurrences of the pattern in the text.

Brute force checks every position: O(n * m) in the worst case.

Rabin-Karp uses a rolling hash to compute the hash of each window in O(1), reducing average time to O(n + m). Only when hashes match do we verify character by character.

---

Rolling Hash: The Core Concept

Polynomial Hash Function

We treat each string as a number in base b (a prime, typically 31 or 37):

hash("abc") = a * b^2 + b * b^1 + c * b^0

Using character codes (a=1, b=2, … z=26):

hash("abc") = 1 * 31^2 + 2 * 31^1 + 3 * 31^0
            = 961 + 62 + 3
            = 1026

All arithmetic is done modulo a large prime p to prevent integer overflow.

The Rolling Update

When the window slides from text[i..i+m-1] to text[i+1..i+m]:

new_hash = (old_hash - text[i] * b^(m-1)) * b + text[i+m]

All mod p. This removes the contribution of the outgoing character and adds the incoming one — in O(1).

---

Basic Implementation

def rabin_karp(text, pattern):
    """
    Find all occurrences of pattern in text using Rabin-Karp.
    Returns list of starting indices.
    """
    n, m = len(text), len(pattern)
    if m > n:
        return []
    
    # Hash parameters
    BASE = 31
    MOD = 10**9 + 7
    
    # Precompute BASE^(m-1) mod MOD
    base_pow = pow(BASE, m - 1, MOD)
    
    # Compute hash of pattern
    pattern_hash = 0
    for ch in pattern:
        pattern_hash = (pattern_hash * BASE + ord(ch) - ord('a') + 1) % MOD
    
    # Compute hash of first window
    window_hash = 0
    for i in range(m):
        window_hash = (window_hash * BASE + ord(text[i]) - ord('a') + 1) % MOD
    
    results = []
    
    for i in range(n - m + 1):
        # Check if hashes match
        if window_hash == pattern_hash:
            # Verify character by character (to handle collisions)
            if text[i:i + m] == pattern:
                results.append(i)
        
        # Roll the hash forward (if not at the last window)
        if i < n - m:
            # Remove leftmost character, add new rightmost character
            outgoing = ord(text[i]) - ord('a') + 1
            incoming = ord(text[i + m]) - ord('a') + 1
            window_hash = (
                (window_hash - outgoing * base_pow) * BASE + incoming
            ) % MOD
    
    return results


# Example
text = "abcabcabc"
pattern = "abc"
matches = rabin_karp(text, pattern)
print(f"Pattern '{pattern}' found at indices: {matches}")
# Pattern 'abc' found at indices: [0, 3, 6]

text2 = "aaaaaaa"
pattern2 = "aaa"
matches2 = rabin_karp(text2, pattern2)
print(f"Pattern '{pattern2}' found at indices: {matches2}")
# Pattern 'aaa' found at indices: [0, 1, 2, 3, 4]

---

Handling Hash Collisions

Hash collisions occur when two different strings produce the same hash. This is why we always verify when hashes match.

Strategy 1: Large Prime Modulus

Using a large prime like 10^9 + 7 makes collisions rare. The probability of a collision between two random strings of length m is approximately 1/MOD.

Strategy 2: Double Hashing

Use two independent hash functions with different bases and moduli. A false match requires a collision in both hashes simultaneously, making the probability approximately 1/MOD1 * 1/MOD2:

def rabin_karp_double_hash(text, pattern):
    """Rabin-Karp with double hashing for collision resistance."""
    n, m = len(text), len(pattern)
    if m > n:
        return []
    
    BASE1, MOD1 = 31, 10**9 + 7
    BASE2, MOD2 = 37, 10**9 + 9
    
    base_pow1 = pow(BASE1, m - 1, MOD1)
    base_pow2 = pow(BASE2, m - 1, MOD2)
    
    def char_val(ch):
        return ord(ch) - ord('a') + 1
    
    # Pattern hashes
    ph1 = ph2 = 0
    for ch in pattern:
        v = char_val(ch)
        ph1 = (ph1 * BASE1 + v) % MOD1
        ph2 = (ph2 * BASE2 + v) % MOD2
    
    # First window hashes
    wh1 = wh2 = 0
    for i in range(m):
        v = char_val(text[i])
        wh1 = (wh1 * BASE1 + v) % MOD1
        wh2 = (wh2 * BASE2 + v) % MOD2
    
    results = []
    
    for i in range(n - m + 1):
        if wh1 == ph1 and wh2 == ph2:
            # Double match -- extremely likely to be a true match
            # Optional: verify for absolute certainty
            if text[i:i + m] == pattern:
                results.append(i)
        
        if i < n - m:
            out_v = char_val(text[i])
            in_v = char_val(text[i + m])
            wh1 = ((wh1 - out_v * base_pow1) * BASE1 + in_v) % MOD1
            wh2 = ((wh2 - out_v * base_pow2) * BASE2 + in_v) % MOD2
    
    return results


text = "the quick brown fox jumps over the lazy dog the fox"
pattern = "the"
print(rabin_karp_double_hash(text, pattern))  # [0, 31, 44]

---

Multiple Pattern Matching

A major advantage of Rabin-Karp over KMP: searching for multiple patterns simultaneously. Compute the hash of each pattern, store them in a set, and check each window against the set.

def rabin_karp_multi(text, patterns):
    """
    Find all occurrences of multiple patterns in text.
    All patterns must have the same length.
    
    Returns dict: pattern -> list of starting indices
    """
    if not patterns:
        return {}
    
    n = len(text)
    m = len(patterns[0])
    
    BASE = 31
    MOD = 10**9 + 7
    base_pow = pow(BASE, m - 1, MOD)
    
    def char_val(ch):
        return ord(ch) - ord('a') + 1
    
    # Compute hash for each pattern
    pattern_hashes = {}
    for pat in patterns:
        h = 0
        for ch in pat:
            h = (h * BASE + char_val(ch)) % MOD
        if h not in pattern_hashes:
            pattern_hashes[h] = []
        pattern_hashes[h].append(pat)
    
    # Compute first window hash
    window_hash = 0
    for i in range(m):
        window_hash = (window_hash * BASE + char_val(text[i])) % MOD
    
    results = {pat: [] for pat in patterns}
    
    for i in range(n - m + 1):
        if window_hash in pattern_hashes:
            # Check all patterns with this hash
            window_text = text[i:i + m]
            for pat in pattern_hashes[window_hash]:
                if window_text == pat:
                    results[pat].append(i)
        
        if i < n - m:
            out_v = char_val(text[i])
            in_v = char_val(text[i + m])
            window_hash = (
                (window_hash - out_v * base_pow) * BASE + in_v
            ) % MOD
    
    return results


text = "abcdefabcxyzabc"
patterns = ["abc", "xyz", "def"]
result = rabin_karp_multi(text, patterns)
for pat, indices in result.items():
    print(f"'{pat}' found at: {indices}")

Output:

'abc' found at: [0, 6, 12]
'xyz' found at: [9]
'def' found at: [3]

Variable-Length Multiple Patterns

For patterns of different lengths, group them by length and run Rabin-Karp once per group:

def rabin_karp_multi_variable(text, patterns):
    """Handle multiple patterns of different lengths."""
    from collections import defaultdict
    
    # Group patterns by length
    by_length = defaultdict(list)
    for pat in patterns:
        by_length[len(pat)].append(pat)
    
    results = {}
    for length, pats in by_length.items():
        group_results = rabin_karp_multi(text, pats)
        results.update(group_results)
    
    return results

---

Substring Hash Queries (Prefix Hash Array)

Precompute hash values for all prefixes. Then the hash of any substring text[l..r] can be computed in O(1):

class StringHasher:
    """Precompute prefix hashes for O(1) substring hash queries."""
    
    def __init__(self, s):
        self.n = len(s)
        self.BASE = 31
        self.MOD = 10**9 + 7
        
        # prefix_hash[i] = hash of s[0..i-1]
        self.prefix_hash = [0] * (self.n + 1)
        self.power = [1] * (self.n + 1)
        
        for i in range(self.n):
            self.prefix_hash[i + 1] = (
                self.prefix_hash[i] * self.BASE + ord(s[i]) - ord('a') + 1
            ) % self.MOD
            self.power[i + 1] = (self.power[i] * self.BASE) % self.MOD
    
    def get_hash(self, l, r):
        """Return hash of s[l..r] (inclusive) in O(1)."""
        raw = (
            self.prefix_hash[r + 1] 
            - self.prefix_hash[l] * self.power[r - l + 1]
        ) % self.MOD
        return raw
    
    def are_equal(self, l1, r1, l2, r2):
        """Check if s[l1..r1] == s[l2..r2] in O(1) (probabilistic)."""
        if r1 - l1 != r2 - l2:
            return False
        return self.get_hash(l1, r1) == self.get_hash(l2, r2)


# Example: find longest repeated substring
s = "banana"
hasher = StringHasher(s)

# Check: is s[1..3] ("ana") == s[3..5] ("ana")?
print(hasher.are_equal(1, 3, 3, 5))  # True

# Check: is s[0..2] ("ban") == s[3..5] ("ana")?
print(hasher.are_equal(0, 2, 3, 5))  # False

---

Plagiarism Detection Use Case

Rabin-Karp is widely used in plagiarism detection tools. The idea: extract “fingerprints” (hash values) of fixed-length chunks from documents and compare them.

def plagiarism_check(doc1, doc2, chunk_size=10):
    """
    Find common chunks between two documents.
    Returns the percentage of doc1 that appears in doc2.
    """
    BASE = 31
    MOD = 10**9 + 7
    
    def char_val(ch):
        return ord(ch) % 256 + 1
    
    # Compute all chunk hashes for doc2
    doc2_hashes = set()
    if len(doc2) >= chunk_size:
        h = 0
        base_pow = pow(BASE, chunk_size - 1, MOD)
        
        for i in range(chunk_size):
            h = (h * BASE + char_val(doc2[i])) % MOD
        doc2_hashes.add(h)
        
        for i in range(len(doc2) - chunk_size):
            h = ((h - char_val(doc2[i]) * base_pow) * BASE 
                 + char_val(doc2[i + chunk_size])) % MOD
            doc2_hashes.add(h)
    
    # Check how many chunks of doc1 appear in doc2
    matches = 0
    total_chunks = 0
    
    if len(doc1) >= chunk_size:
        h = 0
        base_pow = pow(BASE, chunk_size - 1, MOD)
        
        for i in range(chunk_size):
            h = (h * BASE + char_val(doc1[i])) % MOD
        total_chunks += 1
        if h in doc2_hashes:
            matches += 1
        
        for i in range(len(doc1) - chunk_size):
            h = ((h - char_val(doc1[i]) * base_pow) * BASE 
                 + char_val(doc1[i + chunk_size])) % MOD
            total_chunks += 1
            if h in doc2_hashes:
                matches += 1
    
    if total_chunks == 0:
        return 0.0
    return (matches / total_chunks) * 100


doc1 = "the quick brown fox jumps over the lazy dog"
doc2 = "a quick brown fox leaps over the lazy cat"
similarity = plagiarism_check(doc1, doc2, chunk_size=8)
print(f"Similarity: {similarity:.1f}%")

---

Comparison: Rabin-Karp vs KMP vs Brute Force

Feature	Brute Force	KMP	Rabin-Karp
Average time	O(n * m)	O(n + m)	O(n + m)
Worst time	O(n * m)	O(n + m)	O(n * m)
Multiple patterns	O(n * m * k)	O(n * k) or use Aho-Corasick	O(n * k) avg
Space	O(1)	O(m)	O(1)
Implementation	Trivial	Moderate	Simple
Best for	Short strings	Single pattern, guaranteed worst case	Multiple patterns, hashing applications

When to Use Rabin-Karp

• Searching for multiple patterns of the same length
• When you need substring hashing as a building block
• Plagiarism detection and document similarity
• When average-case O(n + m) is sufficient

When to Use KMP

• When you need guaranteed O(n + m) worst case
• Single pattern matching in competitive programming
• When the pattern has many repeated prefixes

---

Common Pitfalls

1. Negative Modular Arithmetic

In Python, (-5) % 7 = 2 (correct). In C++/Java, (-5) % 7 = -5 (wrong for hashing). Always add MOD before taking modulo:

# Safe rolling hash update
window_hash = ((window_hash - outgoing * base_pow % MOD + MOD) * BASE + incoming) % MOD

2. Choosing Bad Parameters

• Base: Use a prime larger than the alphabet size. 31 works for lowercase letters; 131 or 257 for ASCII.
• Modulus: Use a large prime. 10^9 + 7 and 10^9 + 9 are common choices.
• Never use base = 1 or base = 0.

3. Forgetting the Verification Step

Always verify when hashes match. The probability of a spurious match is low but not zero.

---

Practice Problems

1. Repeated String Match (LeetCode 686) — Can pattern B be found in A repeated k times?
2. Longest Duplicate Substring (LeetCode 1044) — Binary search + rolling hash.
3. Implement strStr() (LeetCode 28) — Basic single pattern matching.
4. Longest Happy Prefix (LeetCode 1392) — KMP or rolling hash.
5. Distinct Substrings of Length K — Count distinct hashes for all windows of size K.

---

Key Takeaways

• Rabin-Karp uses a rolling hash to compare window hashes in O(1), avoiding character-by-character comparison.
• The rolling update formula removes the outgoing character and adds the incoming one in constant time.
• Double hashing virtually eliminates collision probability.
• Unlike KMP, Rabin-Karp naturally extends to multiple pattern matching and 2D pattern matching.
• Prefix hash arrays enable O(1) substring hash queries, useful for many string problems.
• Always verify matches character by character to handle the (rare) hash collision case.