Rolling Hash Rabin–Karp · ALG 13.4
Characters are digits, P = 10, so H(x1…xJ) is simply the number x1…xJ mod N. Sliding the window: h := (P·h − σ[i]·PJ + σ[i+J]) mod N. If h = j (the needle's hash), compare the strings: a real occurrence, or a spurious hit that wastes J comparisons.
needle ι = j = H(ι) = window hash h =
real occurrence spurious hit
hash updates 0
occurrences 0
spurious hits 0
character comparisons 0
expected spurious ≈ (S−J+1)/N =
time –
score 0
streak 0
best 0
Press the button. You get the current window and its hash h; type the hash of the next window. Tip: compute mod N as you go, so the numbers stay small. PJ mod N is shown.
Needle ι = , N = , P = 10. Type a haystack of at most 30 digits that contains no occurrence of the needle but makes Rabin–Karp waste as many comparisons as possible on spurious hits.
spurious hits 0
wasted comparisons 0
best 0
Hint: 10 ≡ −1 (mod 11) and 10 ≡ 1 (mod 9). Do these remind you of divisibility rules from school? This is why the book wants PJ to be much larger than N, and N prime with a random P (exercise in ALG 13.4).