Rabin–Karp

The problem it solves

String search, again — but with a different weapon and a different sweet spot. KMP defeats re-reading with a precomputed table; Rabin–Karp sidesteps character comparison almost entirely by comparing numbers. Hash the pattern once. Maintain a hash of the current text window. If the numbers differ, the window provably cannot match — dismissed in O(1), no characters read. If they agree, verify by characters, because different strings can share a hash.

The trick that makes this fast is the rolling hash: when the window slides one position, its hash is updated from the old one in three arithmetic operations — drop the leaving character’s contribution, shift, add the newcomer — regardless of window width. A 1,000-character window costs the same per slide as a 4-character one. That property is what the technique is for, and it pays off brilliantly where KMP cannot: searching for many patterns at once (hash each pattern into a set; roll the text once), finding duplicated substrings, plagiarism shingling, and 2D image-block matching. For one pattern with hard guarantees, KMP wins; for “does any of these ten thousand fragments appear?”, Rabin–Karp is the adult in the room.

The intuition — and where it breaks down

Think of the hash as a cheap fingerprint. Comparing fingerprints is instant; comparing whole documents is slow. So fingerprint the wanted document once, fingerprint each candidate, and fetch the full document only when fingerprints agree. Almost every candidate fails the fingerprint test, so almost all work is O(1) dismissals — the player’s per-window annotations show exactly this rhythm: number, number, number, dismissed, dismissed, verify.

Two asymmetries carry the correctness, and the prediction prompts drill both directions. Unequal hashes are proof: hashing is a function, and a function cannot send equal strings to different values — a differing fingerprint dismisses a window with certainty, zero characters read. Equal hashes are only a hint: the hash maps infinitely many strings onto finitely many values, so by pigeonhole different strings must sometimes collide — the notorious spurious hit. The player ships an engineered-collision preset where three windows share the pattern’s fingerprint and only one survives the character check; watching a spurious hit die at the verify stage is the fastest possible cure for the skip-the-verify bug.

Where the intuition breaks: fingerprints in the analogy are unique; hashes are not, and pretending they are is the whole failure mode. And the analogy hides the rolling part, which is the actual engineering: the window hash is a polynomial b^(m-1)·c0 + … + b·c(m-2) + c(m-1) mod q, so the slide is algebra — subtract the leading term, multiply by b, add the entering character. The visualization uses base 7, mod 97, letters a=1…z=26, precisely so the arithmetic is checkable by hand — the first question asks you to compute a window hash with Horner’s rule, and doing it once anchors everything else.

Loading…

A walkthrough you can check

Base 7, mod 97. Hash abed: fold with Horner — 1; 1·7+2 = 9; 9·7+5 = 68; 68·7+4 = 480 mod 97 = 93.

1. Window abed at 0: hash 93 = target. Verify: a-b-e-d all match — genuine occurrence, 4 character comparisons.
2. Slide to bedn: drop a (subtract 1·7³ = 343 ≡ 52 mod 97), multiply by 7, add n = 14. Three operations; the new number disagrees with 93 — dismissed unread.
3. Every subsequent window: one roll, one integer comparison. Most die by arithmetic. When a later window again hashes to 93, characters decide — and on the engineered preset, dtero and abtuz both hash to the pattern’s value and both fail the verify, spurious hits caught in the act.

Check the counters at the end: total character comparisons stay near m per genuine-or-spurious hit, not per window — the arithmetic did the rest. That final count is the entire economic argument.

The invariant

The maintained hash always equals the true hash of the current window. It holds after the initial Horner fold, and the roll preserves it because the roll is the algebra of the window polynomial: old hash minus the departing character’s b^(m−1) term, times b, plus the arriving character — each step mod q. One subtlety hides in “mod”: after the subtraction the value can be negative in languages with signed remainder, and the +q before reducing is not optional. The invariant is what licenses every dismissal — a window is skipped because its true hash provably differs from the pattern’s.

The correctness statement then splits cleanly: no false negatives ever (equal strings hash equally, so every occurrence reaches the verify stage), and no false positives survive (the verify reads actual characters). Randomness only ever affects speed — how many spurious verifies happen — never the answer. Stating that separation crisply is what distinguishes “knows about hashing” from “understands this algorithm”.

Complexity, derived

The roll makes each of the n−m+1 slides O(1); the initial folds cost O(m). Verifies cost O(m) each and happen once per hash agreement. With a random base/modulus, the probability a non-matching window collides is about 1/q, so expected spurious verifies over the whole text ≈ n/q — negligible for a 61-bit prime. Expected time O(n + m + occurrences·m), space O(1).

The worst case deserves honest airtime: an adversary who knows your modulus can construct a text where every window collides, forcing a verify per slide — O(n·m), the naive bound with extra steps. The defences are standard and worth naming: choose the base (or modulus) randomly at runtime so no fixed input is adversarial, or double-hash (two independent moduli; treat as equal only when both agree), which squares the collision probability. This randomized-versus-adversarial framing — Las Vegas result, Monte Carlo runtime — is exactly the discussion interviewers hope the algorithm provokes.

What people get wrong

• Skipping the verify: reporting hash agreement as a match. Works until the first collision, then corrupts silently. The spurious-hit preset exists to make this bug visceral.
• Overflow in the roll: multiplying before reducing overflows fixed-width integers; every multiply-add must reduce mod q (or use a language with big integers and pay for it).
• Negative modulus: (h - drop) % q is negative in C-family languages when drop > h; add q before reducing. The single most common one-line bug in submitted solutions.
• A tiny or composite modulus: mod 97 is for classrooms (and this visualization); production wants a large random prime, or the collision rate stops being negligible.
• Using it for single-pattern search with guarantees required: that is KMP’s job. Rabin–Karp’s expected-time analysis is the wrong tool where worst-case bounds are contractual.

Implementation notes

Precompute b^(m−1) mod q once — recomputing it per slide quietly reintroduces an O(m) factor. Keep the three roll steps explicit and reduce after each. For 64-bit safety with a large prime, either use 128-bit intermediates, a Mersenne-prime modulus with shift-based reduction, or two 31-bit hashes combined — the double-hash also being your collision defence.

The multi-pattern form is where the algorithm shines: hash all patterns (equal length) into a hash set; roll the text once; verify on set membership. That is O(n + Σmᵢ) for any number of patterns — the thing KMP fundamentally cannot do, and one construction step from Aho–Corasick territory. Longest Duplicate Substring — binary-search the length, Rabin–Karp each candidate length for a repeated window — is the canonical hard interview application, and Repeated DNA Sequences is the same idea with a fixed window of 10.

For 2D pattern matching (find an r×c block in an image), hash each column strip, then roll horizontally over strip-hashes — hashing composing with itself. Mentioning that composition, once, signals the technique has been understood as rolling fingerprints rather than as one memorised loop.

The follow-up questions

Why must equal hashes be verified? Pigeonhole: finitely many hash values, infinitely many strings — different strings must sometimes collide. Equal hashes earn a character check; they never conclude one.

Why do unequal hashes need no verification? Hashing is a function: equal strings cannot produce different outputs. A mismatch is a certificate of non-occurrence, and it is the fast path that makes the algorithm linear in practice.

How does the roll stay O(1) for any window width? The hash is a polynomial in the base; sliding the window is a subtract-shift-add on that polynomial, three operations mod q, independent of m — provided b^(m−1) mod q was precomputed.

Where does Rabin–Karp beat KMP? Many patterns at once, duplicate-substring problems (with binary search on length), shingle-based similarity, and 2D matching. Single pattern, hard worst-case guarantee, streaming: KMP. Both answers, with the reason, is the complete response.