How does Rabin-Karp's rolling hash update each window in O(1), and what does that save?
answer
- the window is a number in some base
- which symbol leaves, which one arrives
- the leading symbol carries the highest place value
- subtract first, then shift, then add
- precompute B^(m-1) before the scan
basics
~20 sA rolling hash derives the next window's hash from the current one in constant time: drop the leading symbol's weighted term, shift the rest, add the trailing symbol. Hashing each window from scratch would cost O(m) per position.
solid answer
~40 sRabin-Karp treats each m-symbol window as a number in some base B, reduced modulo M so values stay bounded. Because the leading symbol contributes exactly `text[s-1] * B^(m-1)`, you can move the window one position with two operations: subtract that term, then multiply by B and add the new trailing symbol — `h = ((h - text[s-1]*high) * B + text[s+m-1]) mod M` with `high = B^(m-1) mod M` precomputed. That is O(1) per position and O(n) hashing over the whole text, against O(n*m) if each window were hashed independently. In a plagiarism screen that fingerprints every 40-symbol window of a submission, that is the difference between one pass and forty. The hash only produces *candidates* — each hash hit still needs a comparison to confirm.
code
pseudocode · 12 lineshigh = B^(m-1) mod M // precomputed once
h = 0
for i in 0..m-1: // hash the first window, O(m)
h = (h * B + text[i]) mod M
check(h, 0)
for s in 1..n-m:
out = text[s-1] // symbol leaving the window
in = text[s+m-1] // symbol entering the window
h = (h - out * high) mod M // remove at its place value
h = (h * B + in) mod M // shift up, append
check(h, s) // hash hit is only a candidate
...go deeper
Recall the shape of the idea: the next window shares all but two symbols with the current one, so its fingerprint can be patched instead of recomputed. Know that this turns O(n*m) hashing into O(n).
Derive the update at the whiteboard. State that the departing symbol sits at place value B^(m-1), that removal precedes the shift, and that B^(m-1) mod M is precomputed once.
Be able to say what the roll does not fix — collisions, verification cost, the adversarial worst case — and to recognise the sliding-window-aggregate pattern when it appears outside string matching.
Frame the choice of fingerprint as a design decision: order-sensitivity, value width, and the resulting candidate rate all follow from it, and the candidate rate is what your verification budget actually pays for.
## The problem the roll solves Suppose you screen an essay for reuse: you fingerprint every 40-symbol window of the submission and look each fingerprint up in a table of fingerprints taken from a reference corpus. There are about n windows in an n-symbol essay, and hashing a window naively reads all 40 of its symbols. That is O(n*m) work just to compute fingerprints — for m = 40 you have read the whole document forty times. The rolling hash removes that factor entirely. ## The window as a number View the window `text[s..s+m-1]` as the digits of a number written in base B, where B is at least the alphabet size and each symbol maps to a numeric code: ``` H(s) = text[s]*B^(m-1) + text[s+1]*B^(m-2) + ... + text[s+m-1]*B^0 ``` All arithmetic is taken modulo a bounded M so the value never outgrows a fixed-width register; that reduction is what keeps every update a constant-time arithmetic operation instead of big-number work. (Choosing good values for B and M is a topic of its own; what matters here is that M bounds the value and therefore creates collisions, which the next paragraph pays for.) ## The update, term by term Move the window one position right. Two things change: `text[s]` leaves, and `text[s+m]` arrives. The departing symbol sits in the highest place, so its contribution is exactly `text[s] * B^(m-1)`. Subtract it. Every remaining symbol must now move up one place value, which is a single multiply by B. Then add the arriving symbol at place value 1: ``` H(s+1) = (H(s) - text[s]*B^(m-1)) * B + text[s+m] ``` Precompute `high = B^(m-1) mod M` once, before the scan, and the whole update is one subtraction, one multiplication, one addition and one reduction — a fixed number of operations regardless of m. Total hashing cost across the text becomes O(n), plus O(m) to hash the pattern and build `high`. Two details bite people. First, **order matters**: you must remove the leading term *before* multiplying by B, otherwise you scale a value that still carries the old leading symbol. Second, the subtraction can go negative under a modulus, so an implementation normalizes back into range; in the mathematical formulation `mod` already yields a non-negative representative. ## What the roll does and does not buy It buys the *fingerprinting*. It does not buy correctness: two different windows can share a hash, because m symbols are being compressed into one bounded number. So a hash hit is a **candidate**, and Rabin-Karp confirms it with an explicit symbol-by-symbol comparison. What the roll buys is that the expensive comparison is reached only at hits rather than at every offset. It also does not change the worst case. If an input drives a hash hit at every offset, every offset pays an O(m) verification and the scan degrades to O(n*m). The bound customarily quoted for Rabin-Karp — O(n+m) — is an *expected* bound that assumes spurious hits are rare. ## Why this shape generalizes The roll is an instance of a broader trick: maintaining an aggregate over a sliding window in O(1) per step by applying the exit and the entry rather than recomputing. A running sum, a running count of a symbol class, a running product all work the same way. The base-B fingerprint is the version that is *order-sensitive* — swap two symbols in the window and the fingerprint changes, which is precisely what a substring search needs and what an order-blind aggregate like a sum could not give you. If you built the same screen on a plain sum of symbol codes, every rearrangement of the same 40 symbols would fingerprint identically and your candidate set would explode. ## The screening picture end to end Hash the pattern (or the whole corpus of known snippets) once. Hash the text's first window directly, in O(m). Then roll across the remaining n-m positions in O(1) each, testing each fingerprint against what you are looking for. On a hit, compare symbols to confirm. Expected total: O(n + m) plus the cost of genuine matches. The multiplier you removed — the m in O(n*m) — is exactly the wasted re-reading of symbols that are already inside the window.
- Why not fingerprint each window with a plain sum of its symbol codes?Because a sum is order-blind: every rearrangement of the same 40 symbols produces the same fingerprint, so candidate hits would fire constantly and each would need an O(m) verification. The base-B weighting makes the fingerprint position-sensitive, which is what substring matching requires — and it is still rollable in O(1), so you give up nothing to get it.
- What breaks if you multiply by the base before removing the leading symbol?You scale a value that still contains the departing symbol's contribution, so the subtraction no longer cancels it — the term is now off by a factor of B and the running hash diverges from the true window hash. From that point every comparison is meaningless: you miss real occurrences rather than merely producing extra candidates. The removal must happen at the old place value.
- What is the total preprocessing cost before the rolling scan can start?O(m) to hash the pattern, O(m) to hash the first window, and O(log m) or O(m) to compute B^(m-1) mod M depending on how you raise it — all O(m) overall, done once. That is why the quoted expected bound is O(n+m) rather than O(n): the m term is the setup, not per-position work.
saying these in an interview costs you the question
- Says the rolling hash removes the need to compare symbols
- Forgets the leading symbol carries weight B^(m-1)
- Multiplies by the base before removing the leading symbol
- Claims the roll makes the worst case O(n+m)
- Thinks the modulus exists to avoid collisions rather than bound values