Rabin-Karp Rolling Hash
Strings: lesson 6 of 11
Slide a number across the text instead of re-reading it.
Lesson 6 of 11 · 5 min
Rabin-Karp Rolling Hash
Step 1 of 8
Find abd inside abcabd. Comparing character by character re-reads the same text over and over.
The Idea
Comparing a pattern against every position re-reads the same characters over and over. Instead, turn each window into one number.
When the window slides, subtract the character leaving, shift the rest up a digit, and add the character arriving. Equal hashes then need one cheap check to confirm.
Real-World Example
Plagiarism and duplicate-file detectors fingerprint text this way. A document is reduced to a stream of rolling hashes, and two documents are compared as numbers — only fingerprint collisions are ever read back as text.
The Code
def find(text, pat, base=26, mod=101):
m, high = len(pat), pow(base, len(pat) - 1, mod)
want = cur = 0
for i in range(m): # hash the pattern and window 0
want = (want * base + ord(pat[i]) - 97) % mod
cur = (cur * base + ord(text[i]) - 97) % mod
for i in range(len(text) - m + 1):
if cur == want and text[i:i + m] == pat: # hashes can collide
return i
if i + m < len(text): # roll one step to the right
cur = (cur - (ord(text[i]) - 97) * high) % mod
cur = (cur * base + ord(text[i + m]) - 97) % mod
return -1
print(find("abcabd", "abd")) # 3Your turn
Put the steps in the right order.
- Compare the window hash with the pattern hash
- Hash the pattern and the first window
- Confirm a hash match by comparing the characters
- Roll the window: drop the old character, add the new one
Mini quiz
1 / 3