Search Pattern (Rabin-Karp Algorithm)
A rolling hash, and the check you cannot skip
Comparing a pattern against every window of the text re-reads the same characters over and over. Rabin-Karp replaces each window with one number and compares numbers instead, then repairs the number as the window slides: the leaving character is subtracted out and the entering one shifted in, so a new window costs a constant amount of work rather than a fresh pass over the pattern. The catch is that a hash squeezes every possible window into a limited range of remainders, so two different strings can land on the same number. This trace uses a deliberately small modulus to make that happen twice: three windows hash equal, and only one of them really is the pattern. The character comparison after a hash hit is what separates them, which is why it belongs in the algorithm and not in a comment.
Details
Animated on: text = "abracadabra", pattern = "cad" — report every index where the pattern starts. Base 26, modulus 79, chosen so a collision actually happens.
Problem:Search Pattern (Rabin-Karp Algorithm)Hard
A rolling hash, and the check you cannot skip
step 1 / 15
Looking for "cad" inside "abracadabra". Comparing the pattern against all 9 windows character by character costs up to 27 comparisons. Instead each window gets ONE number — a hash — and numbers compare in a single operation.
1FUNCTION rabinKarp(text, pat)2 m <- LENGTH(pat)3 high <- POWER(d, m - 1) MOD q4 hp <- HASH(pat)5 hw <- HASH(text[0 .. m - 1])6 FOR i <- 0 TO LENGTH(text) - m7 IF hw = hp8 IF text[i .. i + m - 1] = pat9 APPEND i TO out10 IF i < LENGTH(text) - m11 hw <- ((hw - VAL(text[i]) * high) * d + VAL(text[i + m])) MOD q12 RETURN out
← / → step · space play · Home restart
Every step in words
Show all 15 steps
- Looking for "cad" inside "abracadabra". Comparing the pattern against all 9 windows character by character costs up to 27 comparisons. Instead each window gets ONE number — a hash — and numbers compare in a single operation.
- Build both hashes the same way: read the letters as base-26 digits and keep the remainder mod 79. "cad" gives 12; the first window "abr" gives 43. Keeping only the remainder is what stops the number growing with the pattern length — and it is also what lets two different strings share a hash.
- "abr" hashes to 43, the pattern to 12. Different numbers mean the strings are certainly different, so all 3 character comparisons here are skipped on the strength of one integer compare.
- Rolling the window one step: drop 'a', add 'a', and the hash becomes 12 with one subtract-multiply-add instead of rehashing all 3 characters. "bra" hashes to 12 — exactly the pattern's 12. Equal hashes are a reason to look, not proof: only 79 remainders exist to cover every 3-letter string, so different strings must sometimes share one.
- The character check refuses it: "bra" is not "cad" even though both hash to 12. This is a collision, and it is why the comparison after a hash hit can never be dropped — the hash filters, it does not decide.
- Rolling the window one step: drop 'b', add 'c', and the hash becomes 39 with one subtract-multiply-add instead of rehashing all 3 characters. "rac" hashes to 39, the pattern to 12. Different numbers mean the strings are certainly different, so all 3 character comparisons here are skipped on the strength of one integer compare.
- Rolling the window one step: drop 'r', add 'a', and the hash becomes 52 with one subtract-multiply-add instead of rehashing all 3 characters. "aca" hashes to 52, the pattern to 12. Different numbers mean the strings are certainly different, so all 3 character comparisons here are skipped on the strength of one integer compare.
- Rolling the window one step: drop 'a', add 'd', and the hash becomes 12 with one subtract-multiply-add instead of rehashing all 3 characters. "cad" hashes to 12 — exactly the pattern's 12. Equal hashes are a reason to look, not proof: only 79 remainders exist to cover every 3-letter string, so different strings must sometimes share one.
- Now compare the 3 characters for real: "cad" is "cad", so this hash hit is genuine — the pattern starts at index 4.
- Rolling the window one step: drop 'c', add 'a', and the hash becomes 78 with one subtract-multiply-add instead of rehashing all 3 characters. "ada" hashes to 78, the pattern to 12. Different numbers mean the strings are certainly different, so all 3 character comparisons here are skipped on the strength of one integer compare.
- Rolling the window one step: drop 'a', add 'b', and the hash becomes 54 with one subtract-multiply-add instead of rehashing all 3 characters. "dab" hashes to 54, the pattern to 12. Different numbers mean the strings are certainly different, so all 3 character comparisons here are skipped on the strength of one integer compare.
- Rolling the window one step: drop 'd', add 'r', and the hash becomes 43 with one subtract-multiply-add instead of rehashing all 3 characters. "abr" hashes to 43, the pattern to 12. Different numbers mean the strings are certainly different, so all 3 character comparisons here are skipped on the strength of one integer compare.
- Rolling the window one step: drop 'a', add 'a', and the hash becomes 12 with one subtract-multiply-add instead of rehashing all 3 characters. "bra" hashes to 12 — exactly the pattern's 12. Equal hashes are a reason to look, not proof: only 79 remainders exist to cover every 3-letter string, so different strings must sometimes share one.
- The character check refuses it: "bra" is not "cad" even though both hash to 12. This is a collision, and it is why the comparison after a hash hit can never be dropped — the hash filters, it does not decide.
- All 9 windows scanned. 3 of them hashed equal but only 1 survived the character check, so the 2 collisions cost 6 wasted comparisons and every other window cost a single integer compare. "cad" occurs at index 4.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.