Rabin-Karp
- Algorithms course
- Expert
- Lesson 14/41
- 4 min
Rabin-Karp hash-based string matching.
Rabin-Karp
Rabin-Karp is a hash-based string matching algorithm. It compares the hash of the pattern with the hash of each text window.
If the hashes match there is a possible match; for full confidence we compare characters. Hash collisions are resolved by this verification step.
Thanks to the rolling hash, moving from one window to the next takes O(1); average total complexity is O(n+m).
Rolling hash
The rolling hash subtracts the contribution of the outgoing character and adds that of the incoming one when the window shifts right. This avoids recomputing the hash from scratch.
Formula: h = ((h - ord(text[i-m]) * pow_base) * base + ord(text[i])) % mod, where pow_base = base^(m-1) mod mod.
Taking mod prevents large number overflow; the modulus is usually a large prime.
Practice rabin_karp function
Write rabin_karp(text, pattern). Return the first match index, or -1. Print 7 with print(rabin_karp("merhabatarif", "tarif")).
Starter code
def rabin_karp(text, pattern):
# Hash-based matchingSample solution
def rabin_karp(text, pattern):
# Hash-based matching
base = 256
mod = 101
n, m = len(text), len(pattern)
if m == 0 or m > n:
return -1
ph = 0
th = 0
pow_base = 1
for _ in range(m - 1):
pow_base = (pow_base * base) % mod
for i in range(m):
ph = (ph * base + ord(pattern[i])) % mod
th = (th * base + ord(text[i])) % mod
for i in range(n - m + 1):
if ph == th:
if text[i:i + m] == pattern:
return i
if i < n - m:
th = ((th - ord(text[i]) * pow_base) * base + ord(text[i + m])) % mod
if th < 0:
th += mod
return -1
print(rabin_karp("merhabatarif", "tarif"))Expected output
7
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 hash computation
h = (h * base + ord(text[____)) % modh = (h * base + ord(text[i)) % modExplanation: The i-th character is added to the hash.
2 What is done on a hash collision?
if h == pattern_hash:
...- Match is accepted
- Search stops
- Verify character by character Correct answer
- A new modulus is chosen
Explanation: Hash collisions are verified character by character.
3 Rabin-Karp concepts
| Term | Meaning |
|---|---|
rolling hash |
O(1) shift |
mod |
Large prime |
collision |
Verification needed |
base |
256 characters |