Rabin Karp Algorithm Explained — Rolling Hash for Pattern Matching Interviews

Algorithm Statement#

Rabin Karp searches for occurrences of pattern p (length m) in text t (length n) using a hash function that can slide its window across the text in constant time per step. The classical version uses a polynomial hash:

hash(s) = s[0] * b^(m-1) + s[1] * b^(m-2) + ... + s[m-1] * b^0 (mod q)

When the window shifts right by one character, the new hash is computed in O(1):

new_hash = (old_hash - s[i] * b^(m-1)) * b + s[i+m] (mod q)

When hash(window) == hash(pattern), we verify the match character by character to filter out hash collisions.

Time: O(n + m) expected, O(n * m) worst case under adversarial input. Space: O(1) beyond the input.

Why This Algorithm Matters#

Pattern matching looks like a solved problem until you face multi-pattern variants, plagiarism detectors, or DNA-read alignment with millions of queries. Rabin Karp is the lingua franca for these systems because hashes are composable: you can index every length-k window of a corpus in linear time, store the fingerprints in a hash table, then answer "does pattern p appear?" in expected O(m). That is exactly how MOSS detects copied code, how rsync identifies unchanged file blocks, and how bioinformatics pipelines pre-filter candidate alignments before running expensive Smith-Waterman dynamic programming.

Interviewers at Google, Meta, and Amazon use Rabin Karp problems as a litmus test for hashing fluency. LeetCode 28 (find substring), LC 187 (repeated DNA sequences), LC 1044 (longest duplicate substring), and LC 718 (longest common subarray) all benefit from rolling hash. The pattern reappears in every problem where "compare two substrings in O(1)" turns an O(n^2) brute force into O(n log n) or O(n).

Strategically, mastering rolling hash teaches you to think in fingerprints — a transferable skill that powers Bloom filters, Merkle trees, and content-addressable storage. The same polynomial hash idea, when stored as prefix hashes, gives you O(1) substring equality checks (covered in part 5 of this series).

The Core Insight#

Naive substring matching costs O(n * m) because for every starting position in the text, we re-examine up to m characters. Rabin Karp avoids this by replacing the m-character comparison with a single integer comparison — the hash.

The trick is the rolling hash: when the window slides, we do not recompute the hash from scratch. We subtract the contribution of the leaving character, multiply the remainder by the base, and add the entering character. Modular arithmetic keeps the values bounded.

Two design choices keep collisions rare:

1. Choose a prime modulus (typically 10^9 + 7, 10^9 + 9, or (1 << 61) - 1). A prime modulus distributes hashes uniformly under polynomial inputs.
2. Choose a base larger than the alphabet size (31 for lowercase letters, 131 or 257 for ASCII). The base must be coprime to the modulus, which any prime base satisfies trivially.

Even with these precautions, collisions exist. The classical Rabin Karp does a character-by-character verification on every hash match, keeping correctness deterministic. For competitive programming and high-throughput systems, double hashing (two independent hash pairs) reduces collision probability to roughly 1 / q^2, low enough to skip verification.

The expected O(n + m) bound assumes the hash function distributes uniformly. Adversarial inputs that target a known hash function — like LeetCode's worst-case test suites for pre-2018 hash submissions — can force quadratic behaviour. Randomising the base at runtime defeats those attacks.

Visual Dry Run#

Pattern: "abc", Text: "abdabc". Base b = 26, modulus q = 101. Map a = 1, b = 2, c = 3, d = 4.

hash("abc") = 1 * 26^2 + 2 * 26 + 3 = 676 + 52 + 3 = 731   mod 101 = 24

Window at position 0: "abd"

hash = 1 * 676 + 2 * 26 + 4 = 732   mod 101 = 25
25 != 24, skip.

Slide to position 1: "bda"

Remove 'a': new_hash = (25 - 1 * (676 mod 101)) = (25 - 70) = -45 mod 101 = 56
Multiply by base: 56 * 26 mod 101 = 1456 mod 101 = 38
Add 'a' = 1: 38 + 1 = 39
hash("bda") = 2 * 676 + 4 * 26 + 1 = 1457 mod 101 = 39  (verified)
39 != 24, skip.

Slide to position 2: "dab"

Remove 'b': new_hash = (39 - 2 * 70) mod 101 = -101 mod 101 = 0
Multiply: 0 * 26 = 0
Add 'b' = 2: 2
hash("dab") = 4 * 676 + 1 * 26 + 2 = 2732 mod 101 = 2  (verified)
2 != 24.

Slide to position 3: "abc"

Remove 'd': new_hash = (2 - 4 * 70) mod 101 = (2 - 280) mod 101 = -278 mod 101 = 24
Multiply: 24 * 26 mod 101 = 624 mod 101 = 17
Add 'c' = 3: 20
 
Wait — recompute carefully. The rolling formula is:
new = ((old - leaving * b^(m-1)) * b + entering) mod q
 
old = 2, leaving = 'd' = 4, b^(m-1) = 676 mod 101 = 70, b = 26, entering = 'c' = 3
((2 - 4 * 70) * 26 + 3) mod 101
= ((2 - 280) * 26 + 3) mod 101
= (-278 * 26 + 3) mod 101
= (-7228 + 3) mod 101
= -7225 mod 101
= 24
 
24 == 24 — hash match! Verify "abc" == "abc" character by character. Match confirmed at index 3.

The verification step is essential because two different strings might collide on the hash, especially with a small modulus like 101. Production code uses 64-bit primes where the collision probability is roughly m / 2^61, negligible for any realistic input.

Solution (Optimal)#

Python — Rabin Karp with Verification#

def rabin_karp(text: str, pattern: str) -> list[int]:
    n, m = len(text), len(pattern)
    if m == 0 or m > n:
        return []
    MOD = (1 << 61) - 1   # large Mersenne-like prime
    BASE = 131
    high_power = pow(BASE, m - 1, MOD)
 
    pat_hash = 0
    win_hash = 0
    for i in range(m):
        pat_hash = (pat_hash * BASE + ord(pattern[i])) % MOD
        win_hash = (win_hash * BASE + ord(text[i])) % MOD
 
    matches = []
    for i in range(n - m + 1):
        if win_hash == pat_hash and text[i:i + m] == pattern:
            matches.append(i)
        if i < n - m:
            win_hash = ((win_hash - ord(text[i]) * high_power) * BASE
                        + ord(text[i + m])) % MOD
    return matches

JavaScript — Rabin Karp with Verification#

function rabinKarp(text, pattern) {
  const n = text.length, m = pattern.length;
  if (m === 0 || m > n) return [];
  const MOD = 2147483647n;     // BigInt to avoid 32-bit overflow
  const BASE = 131n;
  let highPower = 1n;
  for (let i = 0; i < m - 1; i++) highPower = (highPower * BASE) % MOD;
 
  let patHash = 0n, winHash = 0n;
  for (let i = 0; i < m; i++) {
    patHash = (patHash * BASE + BigInt(pattern.charCodeAt(i))) % MOD;
    winHash = (winHash * BASE + BigInt(text.charCodeAt(i))) % MOD;
  }
 
  const matches = [];
  for (let i = 0; i <= n - m; i++) {
    if (winHash === patHash && text.slice(i, i + m) === pattern) {
      matches.push(i);
    }
    if (i < n - m) {
      const leaving = BigInt(text.charCodeAt(i));
      const entering = BigInt(text.charCodeAt(i + m));
      winHash = (((winHash - leaving * highPower) % MOD + MOD) % MOD
                 * BASE + entering) % MOD;
    }
  }
  return matches;
}

Complexity: Expected O(n + m). Worst case O(n * m) under adversarial collisions, but a 61-bit prime modulus makes that astronomically unlikely.

Common Mistakes#

Using a small modulus. A 32-bit prime like 10^9 + 7 collides about once per 30000 random strings. For competitive problems that is fine; for production use a 61-bit prime or double hashing. Birthday-bound collisions kick in faster than people expect.

Forgetting to verify on hash match. Without verification, every collision becomes a false positive. Some problems (counting distinct substrings, set membership) tolerate occasional collisions; pattern matching does not.

Negative modular results. Subtracting leaving * high_power can produce a negative intermediate value. In languages with sign-preserving modulo (Python, Ruby) this is fine; in C, C++, Java, and JavaScript, add MOD before taking % MOD to keep the result non-negative.

Recomputing high_power inside the loop. The constant b^(m-1) mod q should be precomputed once. Recomputing it costs an extra log factor per step.

Ignoring overflow in fixed-width languages. (win_hash * BASE) overflows 64-bit signed types when win_hash and BASE are both around q ≈ 2^61. Use __int128 in C++, BigInt in JavaScript, or modular multiplication helpers. Python's arbitrary-precision integers handle this transparently.

Choosing a base equal to the alphabet size. If the base is exactly 26 and you map 'a' -> 0, the leading character contributes nothing to the hash — collisions explode. Use a base larger than the alphabet and shift characters to start from 1.

Interview Tips#

Walk through the rolling formula on the whiteboard before coding. Interviewers want to see that you understand each term: subtract the contribution of the leaving character, multiply remainder by base, add the entering character. State the modulus and base choices and justify them.

Always do a verification step. Hash equality is necessary but not sufficient. If asked why, mention the pigeonhole argument: there are infinitely many strings and only q possible hashes.

For LeetCode 187 (repeated DNA sequences) the verification is implicit because you store actual strings in the seen set keyed by hash. For LC 1044 (longest duplicate substring), binary search on length and check existence using rolling hash — this is one of the cleanest applications of the technique.

If the interviewer asks about the worst case, mention that a known hash function and adversarial input can force O(n * m). The mitigation is randomising the base modulo q at runtime — this is exactly what the LeetCode platform did after a 2017 hack-the-judges incident.

For multi-pattern matching, hash all patterns into a hash table, then slide a window through the text and look up each window's hash. This is the natural generalisation and gets you to expected O(n + total pattern length).

Follow-up Questions#

Q: What is double hashing and when do you need it? A: Use two independent (base, modulus) pairs and treat strings as equal only if both hashes match. Collision probability drops from roughly n^2 / q to n^2 / q^2. Use it whenever you are skipping verification — for counting, set membership, or any algorithm where false positives propagate.

Q: How does Rabin Karp generalise to 2D pattern matching? A: Compute a rolling hash per row to get a column-wise hash strip, then run a second rolling hash vertically over the strip. This finds an m_x by m_y pattern in an n_x by n_y grid in expected O(n_x * n_y).

Q: How does Rabin Karp compare to KMP and Z? A: KMP and Z are deterministic O(n + m) and ideal for single-pattern search. Rabin Karp is expected O(n + m), shines for multi-pattern search, and gives you O(1) substring equality after preprocessing — invaluable in problems beyond pure pattern matching.

Q: What is a Mersenne prime modulus? A: A prime of the form 2^p - 1. (1 << 61) - 1 is one. Modulo such primes can be computed faster than general moduli using bit tricks, which matters in tight inner loops.

Q: Can you use Rabin Karp with arbitrary objects as input? A: Yes — replace ord(c) with any deterministic mapping from the input alphabet to integers. This generalises rolling hash to integer arrays, tuples, and even arbitrary tokens.

Key Takeaways#

• Rabin Karp matches pattern p against text t using a polynomial rolling hash that updates in O(1) per shift, giving expected O(n + m) running time.
• The hash is a fingerprint, not a proof — always verify candidate matches character by character unless you are using strong double hashing.
• Choose a large prime modulus (61-bit Mersenne is excellent), a base larger than the alphabet, and randomise where adversarial input is possible.
• The rolling formula new = ((old - leaving * b^(m-1)) * b + entering) mod q is the heart of the algorithm; precompute b^(m-1) once.
• Rolling hash unlocks repeated DNA sequences, longest duplicate substring, plagiarism detection, and any problem framed as "compare two substrings in O(1)."
• Interview signal: fluency with rolling hash separates candidates who memorise KMP from those who reason about strings as algebraic objects.