Rabin-Karp: Substring Search With a Rolling Hash
The Rabin-Karp algorithm for substring search — how a rolling hash turns O(m) window comparisons into O(1), with a worked trace, JavaScript code, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Searching a document for a phrase is something you do a hundred times a day without thinking. But how do you find every position where a pattern appears inside a longer text — fast — when the text is millions of characters long?
The naive answer compares the pattern against every window of the text, character by character. Rabin-Karp does something cleverer: it turns each window into a single number, and slides that number forward in constant time. Comparing two integers is O(1); comparing two strings is O(m). That swap is the whole trick.
The problem
Given a text and a pattern, return every starting index in text where pattern occurs. Matches may overlap.
Input: text = "ABABA", pattern = "ABA"
Output: [0, 2]
// "ABA" starts at index 0 and again at index 2 — the two occurrences overlap on the middle 'A'The output is a list of positions, not a yes/no. That matters: you can't stop at the first hit, and overlapping matches (like the two ABAs above sharing a character) both count.
The brute force baseline
Line up the pattern at index 0, compare all m characters, slide right by one, repeat. There are roughly n - m + 1 windows and each comparison is up to m characters.
function bruteForce(text, pattern) {
const n = text.length, m = pattern.length;
const matches = [];
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 cost is O(n · m). On a pattern that keeps almost matching — think searching for "AAAAB" in a long run of "AAAAAAAA..." — nearly every window burns the full m comparisons before failing on the last character. That worst case is exactly where the naive approach falls apart.
The key insight: hash the window, not the characters
What if a window's identity were a single number instead of m characters? Then two windows can only match if their numbers match — one integer comparison instead of m character comparisons.
Rabin-Karp treats each length-m string as a base-d number taken modulo a prime q. Here d = 256 (the size of the character alphabet) and q = 101 (a prime that keeps the arithmetic small and collisions rare):
hash("ABA") = (65·256² + 66·256¹ + 65·256⁰) mod 101 = 57The naive move would be to recompute that sum for every window — but that's O(m) per window, buying nothing. The rolling hash is what makes it pay off. When the window slides from [i .. i+m-1] to [i+1 .. i+m], you don't rebuild the number. You subtract the outgoing character's contribution, shift everything up one digit by multiplying by d, and add the incoming character:
newHash = (d · (oldHash − outgoing · h) + incoming) mod q where h = d^(m-1) mod qThat update is O(1), independent of pattern length. The window's hash rolls forward one character at a time, which is where the name comes from.
The optimal solution
This is the exact algorithm the visualizer runs: precompute h = d^(m-1) mod q, seed the pattern hash pHash and the first window hash tHash, then slide. A hash match is only a candidate — because different strings can collide onto the same number mod q, every hash hit is confirmed with a real character comparison before it counts.
var rabinKarp = function (text, pattern) {
let d = 256, q = 101;
let m = pattern.length, n = text.length;
let matches = [];
let pHash = 0, tHash = 0, h = 1;
// h = d^(m-1) mod q
for (let i = 0; i < m - 1; i++) h = (h * d) % q;
// initial hashes for the pattern and the first window
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) {
// verify chars — guard against a spurious hit
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 hash non-negative after subtraction
}
}
return matches;
};Two lines carry the correctness of the whole thing. The text.slice(i, i + m) === pattern check is the collision guard. The if (tHash < 0) tHash += q fixes a JavaScript quirk: subtracting the outgoing character can drive the intermediate value negative, and % in JavaScript keeps the sign, so you nudge it back into [0, q).
Walkthrough
Trace text = "ABABA", pattern = "ABA", with d = 256, q = 101. Precomputation gives h = 256² mod 101 = 88 and pHash = 57. The pattern hash never changes; only tHash rolls.
| i | Window | tHash | pHash | Hashes equal? | Verify | Result |
|---|---|---|---|---|---|---|
| 0 | ABA | 57 | 57 | yes | ABA === ABA | match at 0 |
| — | roll: drop A, add B | 57 → 92 | — | — | — | slide to index 1 |
| 1 | BAB | 92 | 57 | no | skipped | no match |
| — | roll: drop B, add A | 92 → 57 | — | — | — | slide to index 2 |
| 2 | ABA | 57 | 57 | yes | ABA === ABA | match at 2 |
Result: [0, 2]. Notice window i = 1 (BAB) is dismissed on a single integer comparison — 92 ≠ 57 — with zero character work. That's the speedup made concrete: the only windows that ever touch slice are the two whose hashes actually matched. And the roll from 57 → 92 → 57 never recomputes a hash from scratch; each step is one subtract, one multiply, one add.
Complexity
| Metric | Value | Why |
|---|---|---|
| Time (average) | O(n + m) | one O(1) roll per window; hash matches are rare, so verification is negligible |
| Time (worst) | O(n · m) | if every window's hash collides, each triggers an O(m) verify — pathological with a bad q |
| Space | O(1) | a handful of integers plus the output list; no auxiliary table of the text |
The average case assumes a well-chosen prime q, which makes a spurious collision roughly a 1/q event per window. With q = 101 collisions are already uncommon; production implementations use a much larger prime to push worst-case behavior into the realm of the astronomically unlikely.
Common mistakes
- Skipping the character verification. Equal hashes do not guarantee equal strings. Push the index on a hash match alone and you'll report false positives (spurious hits). The
slice(...) === patterncheck is not optional. - Forgetting the negative-hash fixup. After
tHash - outgoing * h, the value can go negative. Withoutif (tHash < 0) tHash += q, JavaScript's sign-preserving%leaves you with a negative hash that never matchespHashagain. - Recomputing the hash instead of rolling it. Rebuilding the window hash with a fresh O(m) loop each slide throws away the entire advantage — you're back to O(n · m) with extra overhead.
- Using a composite or tiny modulus. A non-prime or very small
qclusters hashes and floods you with collisions, dragging every window into the O(m) verify path. - Mishandling
m > nor an empty pattern. If the pattern can't fit, there are zero windows; the loop boundi <= n - mhandlesm > nby never running, but guard empty patterns explicitly if your spec allows them.
Where this pattern shows up next
Rolling hashes and character-level string manipulation power a whole family of problems. These build directly on the ideas here:
- Sum of Beauty of All Substrings — sliding a frequency structure across every substring, the same "update as you slide" mindset as the rolling hash.
- Reverse Words in a String — in-place character surgery and careful index bookkeeping on a text buffer.
- Decode String — parsing and rebuilding strings with a stack, another core string-processing technique.
- Count and Say — run-length encoding a string one pass at a time.
You can also step through the Rabin-Karp visualizer to watch the window hash roll, the collisions flag, and each verified match light up.
FAQ
What is a rolling hash and why is it fast?
A rolling hash represents a fixed-length window of characters as a single number, computed in a base-d positional system modulo a prime q. Its key property is that when the window slides one position, you can update the number in O(1) — subtract the outgoing character's weighted contribution, multiply by the base to shift, and add the incoming character — rather than recomputing the whole thing in O(m). That constant-time update is what lets Rabin-Karp scan an entire text in roughly O(n) on average.
What is a spurious hit in Rabin-Karp?
A spurious hit is when the window hash equals the pattern hash but the actual strings differ. Because many strings can map to the same value modulo q, matching hashes are necessary but not sufficient for a real match. Rabin-Karp handles this by verifying character-by-character on every hash match; only a full character match is recorded. Spurious hits are why the algorithm's worst case is O(n · m), and why choosing a good prime q to keep collisions near 1/q matters.
Why is a prime number used for the modulus?
The prime q controls how evenly hashes spread across the value range. A prime modulus minimizes the clustering and periodic collisions you'd get from a composite modulus, which keeps spurious hits rare and the average running time near O(n + m). A small or non-prime q produces frequent collisions, forcing the O(m) verification step to run constantly and degrading performance toward the brute-force baseline.
When should I use Rabin-Karp over KMP or brute force?
Rabin-Karp shines when you search for multiple patterns at once or need to compare many substrings, because you can hash all patterns and check each window against a set of hashes cheaply. For a single-pattern search with guaranteed linear worst case, KMP is often preferred since Rabin-Karp's worst case is O(n · m). Over plain brute force, Rabin-Karp wins whenever windows tend to almost match, since it replaces most O(m) comparisons with a single O(1) hash check.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.