1. One-Liner
Rabin–Karp compares a rolling hash of each length-m window in the text to the pattern’s hash, verifying with a real string compare on collisions.
2. The Problem It Solves
Find occurrences of pattern P in text T (and variants: multiple patterns, 2D grids). Hashing lets you discard most windows in O(1) amortized work per shift.
3. The Core Idea
Treat substrings as base-B numbers modulo a large prime (or double hash). When the window slides one character, update the hash in constant time instead of recomputing from scratch.
4. How It Works (Table)
| Step | What Happens |
|---|---|
| 1 | Choose base B and modulus M (or two moduli). |
| 2 | Hash P and the first window T[0..m-1]. |
| 3 | For each next window, subtract outgoing char, add incoming char, normalize mod M. |
| 4 | If hashes equal, verify with direct comparison to handle rare collisions. |
5. Dry Run Example
T = "abac", P = "ba", m=2. Hash "ab" then roll to "ba" — match. Single-hash collisions are possible; verification catches false positives.
6. Key Properties
| Property | Value |
|---|---|
| Average time | O(n + m) with good hash |
| Worst case | O(n·m) if many spurious hash hits |
| Multi-pattern | Share rolling on T; check set of hashes |
7. Where It Is Used
| Domain | Use |
|---|---|
| Plagiarism | Fingerprint overlapping windows |
| Competitive programming | Fast substring checks, string sets |
| Bioinformatics | k-mer indexing (with more machinery) |
8. Interview Tips
Discuss collision handling, modular arithmetic (avoid negative), and double hashing. Contrast with KMP’s deterministic comparisons.
9. Comparison with Other Algorithms
| Algorithm | Hash? | Typical strength |
|---|---|---|
| KMP | No | Guaranteed O(n+m) |
| Rabin–Karp | Yes | Simple, batch patterns |
| Boyer–Moore | No | Skips large chunks in practice |
10. Complexity
| Metric | Value |
|---|---|
| Expected time | O(n + m) |
| Worst time | O(n·m) with bad luck / attacks |
| Space | O(1) beyond text/pattern |
Implementation Example (PYTHON)
def rabin_karp(text, pat, base=256, mod=10**9 + 7):
n, m = len(text), len(pat)
if m == 0:
return list(range(n + 1))
if n < m:
return []
h = pow(base, m - 1, mod)
hp = ht = 0
for i in range(m):
hp = (hp * base + ord(pat[i])) % mod
ht = (ht * base + ord(text[i])) % mod
out = []
for i in range(n - m + 1):
if hp == ht and text[i : i + m] == pat:
out.append(i)
if i + m < n:
ht = (base * (ht - ord(text[i]) * h) + ord(text[i + m])) % mod
ht %= mod
return out