Rabin-Karp: Substring Search With a Rolling Hash
How Rabin-Karp finds a pattern inside text in O(n+m) average time using a rolling hash — intuition, JavaScript code, a worked walkthrough, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Searching for a short pattern inside a long block of text feels trivial until you count the comparisons. The naive approach re-checks every character of the pattern at every position — and for a 10,000-character document with a 20-character needle, that's hundreds of thousands of character comparisons.
Rabin-Karp cuts that down by turning each window of text into a single number. Comparing two numbers is O(1); comparing two strings is O(m). The trick is computing the next window's number without rescanning all its characters — a rolling hash that updates in constant time as the window slides.
Master this and you've picked up the core idea behind string fingerprinting, plagiarism detection, and the polynomial-hash technique that shows up all over competitive programming.
The problem
Given a text string and a pattern string, find every starting index in text where pattern occurs.
Input: text = "GEEKS FOR GEEKS", pattern = "GEEK"
Output: [0, 10] // "GEEK" starts at index 0 and index 10The brute-force cost is what we're fighting. For text length n and pattern length m, the naive scan is O(n·m) in the worst case. Rabin-Karp targets O(n + m) on average by making the common case — a window that doesn't match — cost O(1) instead of O(m).
The brute force baseline
Line the pattern up at each starting position and compare character by character:
function bruteForce(text, pattern) {
const matches = [];
const n = text.length, m = pattern.length;
for (let i = 0; i <= n - m; i++) {
let j = 0;
while (j < m && text[i + j] === pattern[j]) j++;
if (j === m) matches.push(i);
}
return matches;
}The killer input is repetitive text like "AAAA...A" searched for "AAAA...B": every window matches m-1 characters before failing on the last one. That's (n - m + 1) × m comparisons — quadratic. Rabin-Karp's job is to reject those near-miss windows in one step.
The key insight: fingerprint the window
Instead of comparing strings, compare hashes. Treat each length-m window as a base-d number modulo a prime q:
hash("AB") = (A_code * d + B_code) mod qTwo different strings can collide onto the same hash, so a hash match isn't proof — it's a signal to verify. But a hash mismatch is a guarantee the strings differ, and that's the win: most windows mismatch and get discarded with a single integer comparison.
The rolling part is what makes it fast. When the window slides from text[i..i+m-1] to text[i+1..i+m], you don't recompute from scratch. You subtract the outgoing character's contribution, shift, and add the incoming character:
tHash = (d * (tHash - outgoing * h) + incoming) mod qHere h = d^(m-1) mod q is the positional weight of the leftmost character — the amount you strip off when it leaves the window. That update is O(1), independent of m.
The optimal solution
This mirrors the algorithm the visualizer traces, with the same variable names (d, q, h, pHash, tHash):
function rabinKarp(text, pattern) {
const d = 256, q = 101; // base = ASCII range, q = prime modulus
const m = pattern.length, n = text.length;
const matches = [];
let pHash = 0, tHash = 0, h = 1;
// h = d^(m-1) % q → weight of the leftmost character
for (let i = 0; i < m - 1; i++) h = (h * d) % q;
// Hash the pattern and the first window (Horner's method), O(m)
for (let i = 0; i < m; i++) {
pHash = (d * pHash + pattern.charCodeAt(i)) % q;
tHash = (d * tHash + text.charCodeAt(i)) % q;
}
for (let i = 0; i <= n - m; i++) {
if (pHash === tHash) {
// hash match is necessary, not sufficient — verify
if (text.slice(i, i + m) === pattern) matches.push(i);
}
if (i < n - m) {
tHash = (d * (tHash - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % q;
if (tHash < 0) tHash += q; // keep the modulus non-negative
}
}
return matches;
}Two lines carry the whole idea. The if (pHash === tHash) gate is the O(1) filter. The rolling-hash line is the O(1) slide. Everything else is bookkeeping.
The if (tHash < 0) tHash += q guard matters because tHash - text.charCodeAt(i) * h can go negative, and JavaScript's % keeps the sign of the dividend. A negative hash would never match pHash, silently breaking correctness.
Walkthrough
Trace text = "ABAB", pattern = "AB" with d = 256, q = 101. Character codes: A = 65, B = 66.
Precompute: h = 256^(2-1) mod 101 = 256 mod 101 = 54.
Initial hashes for "AB": pHash = (256·65 + 66) mod 101 = 16706 mod 101 = 41, and the first window is also "AB" so tHash = 41.
| i | Window | tHash | pHash | Hash? | Verify | matches |
|---|---|---|---|---|---|---|
| 0 | "AB" | 41 | 41 | equal | "AB"=="AB" ✓ | [0] |
| — | roll: drop 'A', add 'A' (idx 2) | 94 | 41 | — | — | [0] |
| 1 | "BA" | 94 | 41 | differ | skipped | [0] |
| — | roll: drop 'B', add 'B' (idx 3) | 41 | 41 | — | — | [0] |
| 2 | "AB" | 41 | 41 | equal | "AB"=="AB" ✓ | [0, 2] |
At i = 1 the hashes differ (94 ≠ 41), so the window is rejected without ever touching its characters — that's the O(1) rejection doing its job. The roll from window "AB" (41) to "BA" is computed as (256·(41 − 65·54) + 65) mod 101, which lands on 94 after the negative-correction step. Final answer: matches at indices [0, 2].
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Brute force | O(n·m) | O(1) | every window can compare up to m chars before failing |
| Rabin-Karp (average) | O(n + m) | O(1) | O(m) to build the first hashes, then O(1) per slide with rare verifications |
| Rabin-Karp (worst case) | O(n·m) | O(1) | pathological input where every window's hash collides |
Space is O(1) beyond the output list — the algorithm carries only a handful of integers. The worst case reappears only when a bad modulus makes nearly every window a spurious hit; a well-chosen prime q makes the collision probability roughly 1/q per window, so the average case dominates in practice.
Common mistakes
- Forgetting the negative guard. Skipping
if (tHash < 0) tHash += qlets the rolling formula produce a negative hash that can never equalpHash, dropping valid matches with no error. - Treating a hash match as a match. Hashes collide. You must verify with
text.slice(i, i + m) === pattern; a "spurious hit" (equal hashes, different characters) is expected, not a bug. - Wrong power for
h. It'sd^(m-1) mod q, notd^m. Off by one power and every roll strips the wrong weight, corrupting all subsequent hashes. - Rolling on the last window. The
if (i < n - m)check prevents readingtext.charCodeAt(i + m)past the end of the string on the final iteration. - Reducing
qto a tiny number for "simplicity". A small modulus spikes the collision rate and drags the average case toward O(n·m). Pick a prime large enough thatd·qstill fits safely in the number type.
Where this pattern shows up next
Rolling hashes and character-level string manipulation power a whole family of problems:
- Sum of Beauty of All Substrings — sweep every substring while maintaining running character counts, the same incremental-state discipline.
- Reverse Words in a String — in-place string surgery where index bookkeeping is everything.
- Decode String — stack-driven parsing that rebuilds strings from an encoded form.
- Count and Say — run-length scanning that generates each term from the last.
You can also step through Rabin-Karp interactively to watch the window slide, the hash roll, and each spurious hit get rejected.
FAQ
Why does Rabin-Karp verify characters after the hashes match?
Because a hash is a lossy fingerprint — many strings map to the same value modulo q. When pHash === tHash, the strings are probably equal, but a collision is possible. The character-by-character check confirms a true match and filters out these "spurious hits". Verification runs in O(m), but only fires on hash matches, which are rare with a good prime, so it barely affects the average cost.
What is the time complexity of Rabin-Karp?
Average and best case are O(n + m): O(m) to hash the pattern and first window, then O(1) work per slide across n positions. The worst case is O(n·m), which only occurs when nearly every window's hash collides with the pattern's — a scenario made astronomically unlikely by choosing a large prime modulus. Extra space is O(1) beyond the list of match indices.
What does the value h = d^(m-1) mod q do?
h is the positional weight of the window's leftmost character. When the window slides, that character leaves, and its contribution to the hash is outgoing_char × h. Subtracting outgoing × h before shifting and adding the new character is exactly what makes the roll O(1). Because the hash is a base-d number, the leftmost of m characters carries the weight d^(m-1), all taken modulo q.
How do I pick the base d and modulus q?
Set d to the size of the character alphabet — 256 covers all ASCII bytes. Choose q as a prime large enough to keep collisions rare, but small enough that d × q never overflows your number type. The classic textbook pair is d = 256, q = 101; production hashers use much larger primes (and sometimes two independent moduli) to drive the collision probability effectively to zero.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.