skip to content

Why must Rabin-Karp compare symbols after two window hashes turn out to be equal?

level: middleimportance: should knowfreq 58%

answer

  1. count the possible windows, count the fingerprints
  2. which direction of the implication actually holds
  3. one-sided error, not two-sided
  4. a mismatch proves difference; a match proves nothing
  5. the confirmation costs O(m) per candidate

basics

~20 s

Equal hashes do not mean equal text. The hash compresses m symbols into one bounded value, so different windows can collide. Rabin-Karp treats a hash match as a candidate only and confirms it with an O(m) comparison.

solid answer

~40 s

The fingerprint maps a huge space — every possible m-symbol window — into a bounded numeric range, so by pigeonhole many windows share a value. The error is **one-sided**: equal windows always hash equal, so a hash *mismatch* proves non-equality in O(1) and the offset can be dropped without touching a symbol. A hash *match* proves nothing on its own, which is why the algorithm confirms it symbol by symbol. Drop that confirmation and you no longer have an exact matcher: a reuse screen would report two unrelated 40-symbol snippets as identical because their fingerprints collided. The confirmation is what makes Rabin-Karp always correct and only probabilistically fast, rather than always fast and occasionally wrong.

go deeper

for a junior

Recall that a hash squeezes many symbols into one number, so two different windows can land on the same value. A hash hit is a candidate to check, not an answer.

for a middle

Explain the one-sided error and derive both halves from it: a fingerprint mismatch rejects an offset in O(1) with certainty, while a fingerprint match needs an O(m) confirmation.

for a senior

Be able to reason about the expected spurious-confirmation rate and about when a deliberately unverified screen is acceptable — a coarse first pass a human reviews — versus when exactness is required.

for a principal

Own the correctness contract: whether the system may report a probabilistic answer at all, what a false positive costs the people downstream, and how that decision is documented rather than inherited from a shortcut.

## Where collisions come from A window of m symbols over an alphabet of size A has A^m possible values. The fingerprint is a single number reduced into a range of size M. Unless M is at least A^m — which it never is, because the whole point is a bounded, fixed-width value — the map cannot be injective. Pigeonhole guarantees collisions exist; a good hash only makes them *unlikely* for any particular pair, never impossible. A subtlety worth naming: the polynomial fingerprint would be injective if you never reduced it, provided the base exceeds the alphabet size — that is just positional notation. The reduction modulo M is what destroys injectivity, and the reduction is non-negotiable because it is what keeps each roll a constant-time operation. ## The error is one-sided, and that asymmetry is the algorithm Equal windows are guaranteed to produce equal fingerprints: the fingerprint is a deterministic function of the symbols. Contrapositive: **different fingerprints prove different windows.** So the scan can reject an offset in O(1) with total confidence and never look at its symbols. The other direction carries no proof. Equal fingerprints are consistent with equal windows *and* with a collision. So a hit is a candidate, and the algorithm spends O(m) confirming it. This asymmetry is the entire economic argument for Rabin-Karp: almost all offsets are rejected for the price of an arithmetic comparison, and only the rare candidate pays the price of reading symbols. ## What skipping verification actually costs you Consider a reuse screen over student submissions that fingerprints every 40-symbol window and flags any window whose fingerprint appears in a corpus index. If it reports on fingerprint equality alone, it produces **false positives**: a passage that shares nothing with the corpus gets flagged because its 40 symbols happened to reduce to the same number as some indexed snippet. Note the direction carefully — you get false *positives*, never false *negatives*. Real reuse is never missed, because identical text always fingerprints identically. That direction is exactly backwards in the usual wrong answer, and an interviewer listens for it. In algorithm-design vocabulary, dropping the confirmation converts a Las Vegas algorithm (always correct, runtime varies) into a Monte Carlo one (fixed fast runtime, small chance of a wrong answer). That trade is sometimes deliberate — a first-pass screen over petabytes where a human reviews the flags anyway may accept it — but it must be a decision, not an oversight, and the flagged output must never be presented as proof. ## The cost of verification, honestly stated Each confirmation is O(m). Two things trigger one: genuine matches, and collisions. Genuine matches are unavoidable work — if the pattern really occurs at many offsets, something has to look at them. Collisions are the avoidable part, and their expected number over an n-symbol text is governed by the fingerprint's range: with a uniform-looking hash into M values and a single pattern, the expected number of spurious confirmations is roughly n/M. With a wide modulus that is negligible; with a narrow one it stops being negligible and verification cost creeps into the inner loop. The quoted expected O(n+m) bound is exactly the statement "spurious confirmations are rare", and it is an assumption about your parameters and your input, not a theorem about all inputs. ## What a good answer sounds like Name the pigeonhole reason collisions must exist. State the one-sided error and derive both consequences from it: O(1) rejection, O(m) confirmation. Say what dropping the confirmation turns the algorithm into and in which direction it goes wrong. Then quantify: expected spurious confirmations scale like n/M, which is why the range matters more than any cleverness in the update. A candidate who says "equal hashes mean equal strings" has not understood what a hash is; a candidate who says "so it might miss matches" has the error direction backwards, which is worse.

  • If verification is skipped, does the screen produce false positives, false negatives, or both?
    False positives only. Identical windows always fingerprint identically, so a genuine occurrence is never missed. Colliding but different windows do fingerprint identically, so unrelated text can be reported as a match. Getting this direction backwards — claiming the scan might miss real matches — is the tell that a candidate has not internalised that the hash is a deterministic function of the symbols.
  • Roughly how many spurious confirmations should a single-pattern scan expect?
    About n/M for a text of n symbols and a fingerprint range of M values, assuming the hash spreads windows evenly. Each costs O(m). With a wide range that term vanishes against the O(n) scan; with a narrow range it can dominate. That ratio, not the elegance of the roll, is what decides whether the expected O(n+m) bound describes your actual runtime.
  • Does the confirmation step change Rabin-Karp's asymptotic worst case?
    Yes — it is what creates the O(n*m) worst case. Without confirmation the scan is O(n) flat and sometimes wrong. With it, an input that produces a hit at every offset pays O(m) at each one. So verification is the price of exactness, and the worst case is the bill when candidates stop being rare.

saying these in an interview costs you the question

  • Says equal hashes prove the windows are equal
  • Claims skipping verification causes missed matches
  • Thinks a prime modulus eliminates collisions entirely
  • Verifies offsets whose hashes already differ
  • Cannot say which direction of the implication is sound

context

resolving links…