Rabin-Karp Algorithm
Find all occurrences of pat in txt using a rolling hash — average O(n+m).
Intuition
Comparing the pattern at every shift is O(n·m). Instead hash the pattern once and hash each window of the text — sliding the window updates the hash in O(1): drop the leading char's contribution, shift, add the new char. Only equal hashes trigger a real comparison.
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
Polynomial hash
hash(s) = Σ s[i]·d^(m−1−i) mod q. Treat the string as a base-d number modulo a prime.
Roll in O(1)
next = (d·(cur − lead·d^(m−1)) + newChar) mod q. One multiply-subtract-add per shift.
Verify on hash hits
Hash collisions are possible → confirm with a direct compare. With a good prime, spurious hits are rare, giving O(n+m) average.
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.