Visual walkthrough — Rabin-Karp — rolling hash, O(n+m) expected

We build up in this order: a string is a number → that number is a hash → the hash of the next window is the old one with three edits → all edge cases → one summary picture.

Step 1 — A string is just a number written in some base

WHAT. Take a short string, say $\text{"cab"}$. Give each letter a number code: $a=0,b=1,c=2,\dots$ (its position in the alphabet). Now we glue those codes together the same way we glue digits to make a decimal number.

WHY. Comparing two numbers is a single machine operation — $O(1)$. Comparing two strings letter by letter is $O(m)$. So the first move is: turn the string into one number. We call that number its hash.

PICTURE. In the figure, $\text{"237"}$ (an ordinary decimal number) sits on top; below it, $\text{"cab"}$ is treated in exactly the same way but in base $b=26$ instead of base $10$.

So for $\text{"cab"}$ with $b=26$: $H(\text{"cab"})=2\cdot 26^2+0\cdot 26^1+1\cdot 26^0=1352+0+1=1353.$

Each symbol is doing a job: $2,0,1$ are the letter codes ($c,a,b$); $26^2,26^1,26^0$ are the place values that keep the letters from getting mixed up.

Step 2 — Keep the number small with a prime $q$

WHAT. For a long string those powers of $b$ explode into astronomically huge numbers. We tame them by working modulo a prime $q$ — meaning: after every operation, keep only the remainder when divided by $q$.

WHY. Two reasons, both drawn in the figure. (1) The number must fit in a machine word, so we cap it. (2) Wrapping around at a large prime scatters strings evenly across $[0,q)$, so unrelated strings rarely land on the same value. A prime (not any old number) avoids nasty patterns where many strings collapse together — see Modular Arithmetic.

PICTURE. The number line from $0$ to $q$ is a circular clock. Big values "wrap around"; two arrows landing on the same tick are a collision.

The collision risk is roughly $1/q$ per comparison (the Birthday Paradox explains why it feels smaller than you'd fear). That is why we later verify on a match — a hash is a filter, never a proof.

Step 3 — Line up the pattern against the first window

WHAT. We have a text $T$ of length $n$ and a pattern $P$ of length $m$. A window is a slice of $T$ that is exactly $m$ letters long, starting at some index $i$: written $T[i..i+m-1]$. We compute $H(P)$ once, then the hash of the first window $H_0=H(T[\mathrm{0..}m-1])$.

WHY. If $H(P)\ne H_0$, the window is definitely not the pattern — skip it for free. If they're equal, it's probably a match, so we do the cheap-in-expectation letter check. We want to test all $n-m+1$ windows, so the real question of the next steps is: how do we get from one window's hash to the next without redoing the whole sum?

PICTURE. The pattern $P$ sits under $T$; a bracket marks window $0$. An amber bracket shows where window $1$ will be — shifted right by one letter.

$H_0=T[0]b^{m-1}+T[1]b^{m-2}+\cdots +T[m-1]b^0(\mathrm{mod}q)$

Every term $T[j]$ is a letter code; every $b^k$ is its place value inside this window.

Step 4 — Drop, Slide, Add: the whole trick in one move

WHAT. Write both window hashes on top of each other and stare at what changed. $H_i=T[i]b^{m-1}+T[i+1]b^{m-2}+\cdots +T[i+m-1]b^0$ $H_{i+1}=T[i+1]b^{m-1}+\cdots +T[i+m-1]b^1+T[i+m]b^0$

Everything in the middle is the same letters — but each has moved up one place (its exponent grew by $1$). Only two things are new: the orange leading term left, the cyan trailing term arrived.

WHY. This is the payoff. Instead of recomputing $m$ terms, we perform three tiny edits:

1. Drop the leading letter's contribution $T[i]b^{m-1}$ (subtract it).
2. Slide everyone left one place (multiply the whole thing by $b$ — that adds $1$ to every exponent at once).
3. Add the new trailing letter $T[i+m]b^0$.

That is $O(1)$ per window. Multiplying by $b$ handles all the middle shifts in a single stroke — that is the clever part.

PICTURE. Three colour-coded arrows: red crosses out the old front letter, a cyan sweep multiplies everything by $b$, an amber box drops in the new letter.

Step 5 — Trace it on a real example (watch the sum stay intact)

WHAT. Search $P=\text{"ab"}$ in $T=\text{"aab"}$ with $b=26,q=101,a=0,b=1$. Here $m=2$, so $P_{\text{high}}=b^1=26$.

• $H(P)=0\cdot 26+1=1$.
• Window $0=\text{"aa"}$: $H_0=0\cdot 26+0=0$. Since $0\ne 1$ → skip (no letters compared!).
• Roll to window $1=\text{"ab"}$ using the boxed formula: $H_1=((0-\underset{T[0]=a}{\underbrace{0}}\cdot 26)\cdot 26+\underset{T[2]=b}{\underbrace{1}})\mathrm{mod}101=1.$
• $H_1=1=H(P)$ → verify the two letters → $\text{"ab"}=\text{"ab"}$ ✓. Match at index $1$.

WHY. Notice we never re-summed the window from scratch — we edited $H_0$ into $H_1$ with one drop, one slide, one add. That is the $O(1)$ step in action.

PICTURE. The text $\text{"aab"}$ with both windows; hashes $0$ and $1$ shown, and the pattern hash $1$ on the side. Green tick on the winning window.

Step 6 — Edge case: the subtraction goes negative

WHAT. When we compute $H_i-T[i]\cdot P_{\text{high}}$ under mod arithmetic, $H_i$ (already reduced to $[0,q)$) may be smaller than the term we subtract. The raw result is negative — an illegal state for our hash, which must live in $[0,q)$.

WHY. In real modular arithmetic $-5\equiv q-5$, but most programming languages return a negative remainder for the $\%$ operator. If we leave it negative, later comparisons break silently. The fix is to add a full $q$ back before the final mod.

PICTURE. On the clock circle, an arrow steps backwards past $0$ into negative territory; a second amber arrow adds $q$ to bring it onto the correct positive tick — same point on the circle.

Step 7 — Degenerate windows: $m=n$, $m>n$, and the collision case

WHAT & WHY. Three boundary scenarios the reader will eventually hit:

• $m=n$ (pattern as long as text): there is exactly one window. No rolling happens — we just compare $H(P)$ with $H(T)$ once, then verify. The loop body never fires; the algorithm degrades gracefully to a single check.
• $m>n$ (pattern longer than text): zero windows exist. We must return "no match" before touching the loop — otherwise we index past the end of $T$.
• Collision (different strings, equal hash): the whole reason verification exists. Two distinct windows can land on the same tick of the clock from Step 2. Hashes match → we compare letters → mismatch → we correctly reject. No false match is ever reported.

PICTURE. Three mini-panels: (a) $m=n$ single bracket, (b) $m>n$ pattern overhanging with a red "no window" stamp, (c) two different strings both pointing to one clock tick with a red "verify saves us" arrow.

The one-picture summary

Everything at once: the text as a row of letters, the window as a bracket that hops right one step at a time, each hop labelled Drop · Slide · Add, each landing checked against the clock of residues mod $q$, and a green verify only where hashes coincide.

$\underset{\text{once, }O(m)}{\underbrace{H(P)}}\text{vs}\underset{\text{once, }O(m)}{\underbrace{H_0}}\underset{O(1)}{\overset{\text{Drop⋅Slide⋅Add}}{\to }}{H}_1\underset{O(1)}{\to }{H}_2\to \cdots \to H_{n-m}$

Total: $O(m)$ setup + $O(n)$ rolling + a tiny expected verification cost $=O(n+m)$ expected.

Recall

Connections

• Parent · Rabin-Karp — the algorithm this page derives
• Hashing — why the polynomial shape spreads strings apart
• Modular Arithmetic — the clock, primes, and the non-negative fix
• String Hashing for Substring Comparison — same Drop·Slide·Add for $O(1)$ range equality
• Knuth-Morris-Pratt · Z-Algorithm — collision-free linear alternatives
• Birthday Paradox — the intuition behind collision odds