Rabin-Karp finds a pattern inside a longer text by comparing numbers instead of strings. It hashes the pattern once, then slides a fixed-width window across the text and compares the window's hash to the pattern's hash. The trick that makes it fast is a rolling hash: when the window shifts right by one, you update the hash in O(1) instead of re-reading every character.
Core idea. Turn each length-m window of the text into a number with a polynomial hash. When the
window slides, remove the leaving character and add the entering one to roll the hash forward in
O(1). Only when a window hash equals the pattern hash do you actually compare characters — that final
check rules out coincidental collisions. Searching "abd" in "abcabd" finds a match at index 3.
Intuition
Comparing two strings character by character at every position is O(n·m) — slow when the text is long. A hash collapses a whole window into a single integer, so most positions can be rejected with one cheap integer comparison.
But re-hashing each window from scratch would still cost O(m) per position. The insight: consecutive windows overlap almost entirely. A polynomial hash treats the window like a number written in base B — h = c0·B^(m-1) + c1·B^(m-2) + ... + c(m-1). Sliding right means dropping the most-significant digit, shifting everyone left (multiply by B), and appending the new digit. That is three arithmetic operations, independent of m.
Walk through it
Step through the animation on the right. The top row is the text, the bottom row is the pattern. The lo / hi pointers bracket the current window, and the metric line shows window hash vs pattern hash.
First we hash the pattern "abd" once to get its fingerprint. Then we hash the very first window "abc" and compare — the numbers differ, so no match. Each roll step slides the window one cell right and updates the hash in O(1) by removing the leaving character and adding the entering one. When the window reaches "abd", its hash equals the pattern hash, so we trigger a verify step: we compare the characters directly, confirm they really match, and report index 3. The verify guards against the rare case where two different strings hash to the same number (a collision).
The code, line by line
def rabin_karp(text, pat):
m, n = len(pat), len(text)
pat_hash = hash_str(pat[:m])
high = (BASE ** (m - 1)) % MOD
win = hash_str(text[:m])
for lo in range(n - m + 1):
if lo > 0:
left = ord(text[lo - 1]) - 97
win = (win - left * high) % MOD
win = (win * BASE + ord(text[lo + m - 1]) - 97) % MOD
if win == pat_hash:
if text[lo:lo + m] == pat:
return lo
return -1pat_hashis computed once;highisBASE^(m-1) mod MOD, the weight of the leading character so we can subtract it cleanly when it leaves.winholds the hash of the current window; we seed it with the firstmcharacters before the loop.- Inside the loop, for every position after the first we roll: line 9 subtracts the leaving character's weighted contribution, and line 10 multiplies by
BASEand adds the entering character. That is the O(1) update. if win == pat_hashis only a candidate match. Because hashes can collide, line 12 verifies the actual substring before returninglo.- If the loop finishes with no verified match, return
-1.
Complexity
| Case | Time | Notes |
|---|---|---|
| Average / best | O(n + m) (moderate) | one hash per position, O(1) rolls, few collisions |
| Worst | O(n * m) (moderate) | adversarial input forces a full verify at every position |
O(1) (fast)On typical input, collisions are rare, so the character verify almost never runs and each of the n - m + 1 positions costs O(1). A pathological text (or a bad hash) can force the verify at every position, degrading to O(n·m) — the same as naive search.
When to use / pitfalls
Rabin-Karp shines for multi-pattern search (hash many patterns, look each window up in a set in O(1)) and for 2-D pattern matching. For single-pattern search, KMP gives a guaranteed O(n + m) with no collisions — mention both if asked, then pick KMP when worst-case matters and Rabin-Karp when you have many patterns or need rolling hashes for substring fingerprints.
Two traps. First, never skip the character verify — equal hashes are necessary but not sufficient, and
returning on a hash match alone is a correctness bug. Second, do the modular arithmetic carefully: after
subtracting the leaving character you can get a negative value, so reduce with % MOD and add MOD back
if needed. Choose a large prime MOD and a sensible BASE to keep collisions rare.
Practice
When the window slides from text[lo-1..] to text[lo..], how many character reads does updating the rolling hash need, regardless of the pattern length m?
1. Why does Rabin-Karp still compare characters after a hash match?
2. What makes the rolling hash update O(1) per slide?
3. What is the average-case time complexity of Rabin-Karp for one pattern?
4. For which task is Rabin-Karp especially well suited compared to KMP?