Rabin-Karp Algorithm
Rabin-Karp Algorithm: find all occurrences of pat in txt using a rolling hash — average O(n+m).
- 1 <= |txt| <= 10⁵
- 1 <= |pat| <= |txt|
- Both strings consist of lowercase English letters
Intuition
The rabin karp algorithm finds every occurrence of a pattern in a text. The naive approach compares the pattern against the text at each shift, costing O(n·m) because a near-match can burn m comparisons before failing on the last character.
The idea is to compare numbers instead of strings. Hash the pattern once, then hash each window of the text and compare hashes. A number comparison is O(1) regardless of pattern length.
That only helps if hashing a window is cheap, and hashing each one from scratch would cost m per window — no better than before. The trick is the rolling hash: adjacent windows share all but two characters, so the next hash can be derived from the current one in constant time. Drop the leading character's contribution, shift the remaining value up one position, and add the new trailing character.
Treating the string as a base-d number modulo a prime q makes that arithmetic work out:
- hash = (d · (hash − leadChar · d^(m−1)) + newChar) mod q — one multiply, one subtract, one add per shift.
The modulus keeps values in range but introduces collisions: two different strings can share a hash. So a hash match is a candidate, not a result — always verify with a direct comparison. With a good prime, spurious hits are rare enough that the average cost stays O(n + m), though a pathological input can still force O(n·m).
Hash the pattern once, then roll a hash across the text so each window costs O(1) to compute rather than O(m). The rolling update — subtract the leaving character's contribution, shift, add the entering one — is the reusable idea. Because hashes can collide, a match must always be confirmed by a real comparison.
Approach
Before reading on: price up what counting everything costs here, then ask what you are recomputing on every character that could be carried instead. Aim for O(n+m) average time and O(1) space.
Hash the pattern and the first window
Compute a polynomial hash of the pattern and of the text's first m characters using the same base and modulus. From here the pattern's hash never changes — only the window's does.
Understand the polynomial hash
Treat the string as a base-d number: hash(s) = Σ s[i] · d^(m−1−i) mod q. The positional weights are what make it order-sensitive — without them, anagrams would collide constantly and every window would need verifying.
Roll the hash in constant time
Subtract the leading character's contribution lead · d^(m−1), multiply by d to shift positions, add the incoming character, and take the modulus. Precompute d^(m−1) mod q once rather than recalculating it per shift.
Handle the negative intermediate
After subtracting the leading term the value can go negative in languages where % keeps the sign, such as C++ and Java. Add q before taking the modulus — this is the single most common Rabin-Karp bug, and it produces silent misses rather than a crash.
Verify every hash match
Equal hashes mean the strings might match. Compare them character by character to confirm. Skipping this makes the algorithm wrong, not merely approximate — a collision would report a match that is not there.
Cost and when it degrades
Average time is O(n + m), since verification is rare with a well-chosen prime. The worst case is O(n·m) when every window collides — contrived, but the reason KMP is preferred for guaranteed linear time. Space is O(1).
Solution & live demo
Common pitfalls
Trusting the hash without verifying
if p == t:
hits.append(s)if p == t and txt[s:s+m] == pat:
hits.append(s)Different strings can hash to the same value modulo q, so a hash match is only a candidate. Skipping the confirmation reports false positives — the verification is what makes the algorithm correct rather than probabilistic.
Recomputing the window hash from scratch
t = 0
for i in range(m):
t = (d * t + ord(txt[s+i])) % qt = (d * (t - ord(txt[s]) * h) + ord(txt[s + m])) % q
That's O(m) per position and gives away the whole advantage — you may as well compare strings directly. The rolling update is O(1) because it only adjusts for the two characters that changed.
Using the wrong power for the leading character
h = d ** m
h = pow(d, m - 1, q)
The outgoing character sits at the highest position of an m-digit number, whose weight is d^(m-1). Using d^m removes a value that was never there and the rolling hash desynchronises from the window.
Edge cases
The verification compare rejects it — correctness never depends on the hash.
No windows exist; return no matches.