Rabin-Karp Algorithm
Find all occurrences of pat in txt using a rolling hash — average O(n+m).
02
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.
03
Approach
1
Polynomial hash
hash(s) = Σ s[i]·d^(m−1−i) mod q. Treat the string as a base-d number modulo a prime.
2
Roll in O(1)
next = (d·(cur − lead·d^(m−1)) + newChar) mod q. One multiply-subtract-add per shift.
3
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.
04
Solution & live demo
python
▶1def rabin_karp(txt, pat, d=256, q=101):
▶2 n, m = len(txt), len(pat)
▶3 if m > n: return []
▶4 h = pow(d, m - 1, q)
▶5 p = t = 0
▶6 for i in range(m):
▶7 p = (d * p + ord(pat[i])) % q
▶8 t = (d * t + ord(txt[i])) % q
▶9 hits = []
▶10 for s in range(n - m + 1):
▶11 if p == t and txt[s:s+m] == pat:
▶12 hits.append(s)
▶13 if s < n - m:
▶14 t = (d * (t - ord(txt[s]) * h) + ord(txt[s + m])) % q
▶15 return hits
05
Edge cases
Hash collision without a match
The verification compare rejects it — correctness never depends on the hash.
Pattern longer than text
No windows exist; return no matches.
06
Complexity
Time
O(n+m) average
Space
O(1)
O(n·m) worst case under adversarial collisions.