Rabin-Karp
mediumRolling the window's hash costs O(1) instead of O(m). Equal hashes are a hint, not a proof - watch a deliberate collision get caught by the verification step.
O(n + m)Worst O(n·m)Space O(1)What to notice
The rolling hash is the whole idea
Recomputing a window's hash from scratch costs O(m). Rolling it - subtract the departing character's contribution, multiply, add the arriving one - costs O(1). Same trick as a sliding-window sum, applied to a polynomial.
Equal hashes are a hint, not a proof
Different strings can hash the same. The verification step is mandatory; skip it and the algorithm reports matches that are not there. Watch for a spurious hit highlighted in amber.
O(n + m) expected, O(n·m) worst case
With a good modulus collisions are rare and verification almost never runs. An adversary who knows your hash parameters can force a collision at every position - which is why the modulus should be large and, ideally, randomised.
Where it beats KMP: many patterns at once
Hash all k same-length patterns into a set, then roll one window across the text and check membership. That is O(n + total pattern length) for any number of patterns - something KMP cannot do without running k separate scans.
Saved in this browser - no sign-up, nothing sent anywhere.
How Rabin-Karp works
Compare numbers before characters. Hash the pattern once, keep a hash of the current m-character window of the text, and only compare characters when the two numbers agree. The saving is in the slide: subtract the departing character's contribution, multiply by the base, add the arriving character - O(1) per step, against the O(m) a recomputed hash would cost.
The hash reads the window as a number: each character is a digit in some base, reduced by a modulus. The visualizer deliberately runs with base 7 mod 101 so that collisions actually appear on screen; the reference code uses base 256 mod 1,000,000,007, where a random collision is roughly a one-in-a-billion event per window. Either way, equal hashes are a hint, not a proof.
Verification keeps it honest: on a hash hit, compare character by character before reporting. That step is also where the worst case lives - an adversary who knows base and modulus can force collisions at every position, driving cost to O(n·m). Its unique strength is multi-pattern search: hash k patterns into a set and roll one window past all of them at once.
Step by step
- Search for ab in abab with base 7, mod 101, and letter codes a = 1, b = 2. The pattern hashes to 1·7 + 2 = 9.
- The first window ab also hashes to 9. Equal hashes trigger verification: a matches a, b matches b - a confirmed hit at index 0.
- Roll to window ba: subtract the leading a's contribution 1·7, multiply by 7, add the incoming a. (9 - 7)·7 + 1 = 15.
- 15 differs from the pattern's 9, so offset 1 is rejected by one integer comparison - no characters read at all.
- Roll again: (15 - 14)·7 + 2 = 9. Hashes agree at offset 2, verification passes, second hit. Result: matches at 0 and 2.
- With a modulus this small, an unrelated window can also hash to 9 - the verification step exists to catch exactly that impostor, shown in amber in the player.
Complexity
| Average time | O(n + m) |
|---|---|
| Worst case time | O(n·m) |
| Space | O(1) |
The worst case needs a hash hit to verify at nearly every position - a genuinely repetitive text, or collisions, which a large modulus makes unlikely.
Reference implementation
Python
def rabin_karp(text, pattern, base=256, mod=1_000_000_007):
n, m = len(text), len(pattern)
if m > n:
return []
high = pow(base, m - 1, mod)
ph = wh = 0
for i in range(m): # hash pattern and first window
ph = (ph * base + ord(pattern[i])) % mod
wh = (wh * base + ord(text[i])) % mod
hits = []
for i in range(n - m + 1):
if wh == ph and text[i:i + m] == pattern: # verify! hashes collide
hits.append(i)
if i < n - m: # roll the window in O(1)
wh = ((wh - ord(text[i]) * high) * base + ord(text[i + m])) % mod
return hitsJavaScript
function rabinKarp(text, pattern, base = 256, mod = 1_000_000_007) {
const n = text.length, m = pattern.length;
if (m > n) return [];
let high = 1;
for (let i = 0; i < m - 1; i++) high = (high * base) % mod;
let ph = 0, wh = 0;
for (let i = 0; i < m; i++) {
ph = (ph * base + pattern.charCodeAt(i)) % mod;
wh = (wh * base + text.charCodeAt(i)) % mod;
}
const hits = [];
for (let i = 0; i <= n - m; i++) {
if (wh === ph && text.slice(i, i + m) === pattern) hits.push(i);
if (i < n - m) {
wh = ((wh - text.charCodeAt(i) * high) % mod + mod) % mod;
wh = (wh * base + text.charCodeAt(i + m)) % mod;
}
}
return hits;
}Common pitfalls
- Skipping verification. Equal hashes are consistent with a match, not proof of one - unverified Rabin-Karp will eventually report a position where the window merely collides with the pattern.
- Forgetting the negative fix after the subtraction. In JavaScript, C, or Java the % operator can return negatives, so the roll needs ((wh - out·high) % mod + mod) % mod.
- Computing base to the power m - 1 without the modulus. The precomputed high value must be reduced at every multiply, or it overflows long before patterns get interesting.
- Using a small or predictable modulus against adversarial input. Anyone who knows base and mod can build a text that collides at every window, forcing the O(n·m) worst case.
Where it is used
- Plagiarism and duplicate-content detection - fingerprint every window of every document once, then compare hashes across an entire corpus.
- Multi-pattern search: hash k same-length patterns into a set and roll one window - O(n + total pattern length) regardless of k.
- Longest duplicate substring and its relatives: binary search over the answer length with a rolling hash inside is the standard approach.
- Genomic k-mer screening, where fixed-length windows slide across long sequences and neighbouring windows share all but one character.
Frequently asked questions
What is the time and space complexity of Rabin-Karp?
Average O(n + m) with O(1) extra space: O(m) to hash the pattern and first window, then O(1) per roll for the remaining positions, with verification rarely firing. Worst case is O(n·m), reached when nearly every position needs verifying - a genuinely repetitive text such as aaa in a run of a's, or a collision at every position, which a large modulus makes vanishingly unlikely.
What happens when two different strings get the same hash?
A collision: the hash check passes and the character-by-character verification then fails, so nothing is reported. The visualizer runs base 7 mod 101 precisely so you can watch one happen. With mod 1,000,000,007 a random window collides with the pattern roughly once per billion windows.
Why does the hash need both a base and a modulus?
The base weights positions, so ab and ba hash differently - the window is read as a number written in that base. The modulus keeps the number small enough for machine arithmetic. Both are needed for the roll: subtract, multiply, add, reduce, all in constant time.
When is Rabin-Karp better than KMP?
When several patterns of one length are searched together: hash them into a set, roll a single window, and test membership at each position. KMP needs a separate scan per pattern (or the jump to Aho-Corasick). For a single pattern with a required worst-case bound, KMP wins.