Rabin-Karp String Matching: Rolling Hashes, Spurious Hits & Real-World Performance

Every time your IDE finds all occurrences of a variable name, every time a plagiarism detector scans a 50,000-word essay, every time a database engine hunts for a substring — a string matching algorithm is doing the heavy lifting. Most developers reach for the naive O(n·m) approach without realising it silently tanks performance the moment pattern or text grows large. Rabin-Karp isn't just a clever trick; it's the algorithm underpinning multi-pattern search in tools like grep, antivirus scanners, and bioinformatics pipelines.

The core problem Rabin-Karp solves is the sliding-window comparison bottleneck. In a naive search, shifting the window one character to the right means re-comparing up to m characters all over again. Rabin-Karp replaces that character-by-character re-comparison with a single arithmetic operation — subtracting the outgoing character's contribution and adding the incoming one. This 'rolling hash' trick keeps the average case firmly at O(n + m) while letting you search for multiple patterns simultaneously by checking each window's hash against a set of pattern hashes in O(1).

By the end of this article you'll understand exactly how the polynomial rolling hash is constructed and why each design choice matters, how to handle hash collisions (spurious hits) correctly, how to implement a production-safe version in Java with meaningful variable names and real output, and when Rabin-Karp beats KMP or Boyer-Moore — and when it doesn't. You'll also walk away knowing the three gotchas that trip up even experienced engineers implementing this for the first time.

What is Rabin-Karp? — Plain English

Rabin-Karp is a string-matching algorithm that uses hashing to find a pattern within a text. Instead of comparing the pattern character-by-character against every text window, it first computes a hash of the pattern and a rolling hash of each text window of the same length. Only when hashes match does it do a character-by-character confirmation. This makes the average case O(n+m), and the rolling hash allows moving the window one character to the right in O(1) time.

The real power of Rabin-Karp is when you need to search for multiple patterns simultaneously: store all pattern hashes in a set, then each rolling window hash lookup is O(1). This is why plagiarism-detection tools and code duplication finders often use Rabin-Karp.

How Rabin-Karp Works — Step by Step

1. Choose a base (e.g., 31 or 256) and a large prime modulus to reduce collisions.
2. Compute the hash of the pattern and the hash of the first window of text (length m).
3. For each window position i from 0 to n-m:
4. a. If hash(text[i..i+m-1]) == hash(pattern):
5. - Confirm with a character-by-character comparison (handles hash collisions).
6. - If equal, record a match at index i.
7. b. Slide the window right: remove text[i], add text[i+m].
8. Rolling hash update: h = (h - text[i] base^(m-1)) base + text[i+m] (mod prime)
9. Return all match positions.

Time complexity: O(n+m) average case. O(n*m) worst case (if every window causes a hash collision requiring full comparison — rare with a good hash function).

Worked Example — Tracing the Algorithm

Pattern: 'abc' (m=3). Text: 'xabcabc'. Base=256, Prime=101.

Hash of 'abc': h = (ord('a')256^2 + ord('b')256 + ord('c')) % 101 = (9765536 + 98256 + 99) % 101 = (6356992 + 25088 + 99) % 101 = 6382179 % 101 = 54

Window 0: 'xab'. hash != 54. Slide. Window 1: 'abc'. hash == 54. Confirm 'abc'=='abc'. MATCH at index 1. Window 2: 'bca'. hash != 54. Slide. Window 3: 'cab'. hash != 54. Slide. Window 4: 'abc'. hash == 54. Confirm 'abc'=='abc'. MATCH at index 4.

Matches found at indices 1 and 4.

Implementation

The following implementation demonstrates Rabin-Karp with clear comments.

def rabin_karp(text, pattern, base=256, prime=101):
    n, m = len(text), len(pattern)
    if m > n: return []

    # Precompute base^(m-1) mod prime for rolling hash removal
    h = pow(base, m - 1, prime)

    pattern_hash = 0
    window_hash  = 0
    for i in range(m):
        pattern_hash = (base * pattern_hash + ord(pattern[i])) % prime
        window_hash  = (base * window_hash  + ord(text[i]))    % prime

    matches = []
    for i in range(n - m + 1):
        if window_hash == pattern_hash:
            if text[i:i+m] == pattern:  # confirm to handle collisions
                matches.append(i)
        if i < n - m:
            # Roll the window: remove text[i], add text[i+m]
            window_hash = (base * (window_hash - ord(text[i]) * h) + ord(text[i+m])) % prime
            if window_hash < 0:
                window_hash += prime
    return matches

print(rabin_karp('xabcabc', 'abc'))

Frequently Asked Questions