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

WHAT problem are we solving?

Given a text $T$ of length $n$ and a pattern $P$ of length $m$ , find every position $i$ where $P$ occurs in $T$ (i.e. $T[i..i+m-1] = P$ ).

The naive approach checks each of the $n-m+1$ windows by comparing $m$ characters → $O(nm)$ worst case. Rabin-Karp aims for $O(n+m)$ expected.

If $h(P) \ne h(\text{window})$ , the strings are definitely different — skip instantly. If $h(P) = h(\text{window})$ , they are probably equal, so we verify. Equal strings always have equal hashes, so we never miss a match. The only risk is a false positive (collision), which costs an extra $O(m)$ check.

HOW: building the hash from first principles

Treat a string as a number in base $b$ (think of digits). For a string $s$ of length $m$ with character codes $s_0, s_1, \dots, s_{m-1}$ :

H(s) = s_0 b^{m-1} + s_1 b^{m-2} + \dots + s_{m-1} b^{0} \pmod{q}

Deriving the rolling update

We have the hash of window $T[i..i+m-1]$ :

H_i = T[i]\,b^{m-1} + T[i+1]\,b^{m-2} + \dots + T[i+m-1]\,b^{0}

We want $H_{i+1}$ for window $T[i+1..i+m]$ . Three operations:

Remove the leading char $T[i]$ , which contributes $T[i]\,b^{m-1}$ .
Shift left (multiply by $b$ ): every remaining term's exponent goes up by 1.
Add the new trailing char $T[i+m]\,b^0$ .

So:

\boxed{H_{i+1} = \big(H_i - T[i]\,b^{m-1}\big)\cdot b + T[i+m] \pmod q}

Why this step? Subtracting kills the old high-order digit; multiplying by $b$ slides everyone over; adding inserts the new low-order digit. All $O(1)$ — that's the whole speedup.

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

Complexity — WHY $O(n+m)$ expected

Precompute $h(P)$ and $h(T[0..m-1])$ : $O(m)$ .
Slide across $n-m+1$ windows, each update $O(1)$ : $O(n)$ .
Verify only on hash matches. With a good prime $q$ , the chance of a spurious match is about $1/q$ , so expected verification cost is tiny → total $O(n+m)$ expected.
Worst case $O(nm)$ (every window collides, e.g. adversarial input with small $q$ ).

Worked Example 1 — tiny by hand

Search $P = \texttt{"ab"}$ in $T = \texttt{"aab"}$ . Let base $b = 26$ , $q = 101$ , code $a=0, b=1$ .

$h(P) = 0\cdot26 + 1 = 1$ .
Window 0 = "aa": $0\cdot26 + 0 = 0$ . Why? digits are $a=0,a=0$ . $0 \ne 1$ → skip.
Roll to window 1 = "ab": $P_{\text{high}} = b^{1} = 26$ . $H_1 = (0 - T[0]\cdot26)\cdot26 + T[2] = (0 - 0)\cdot26 + 1 = 1$ . Why? removed leading 'a'(=0), shifted, added 'b'(=1). Matches $h(P)=1$ → verify → "ab"=="ab" ✓. Match at index 1.

Worked Example 2 — a collision (steel-man)

$T = \texttt{"xy"}$ , $P = \texttt{"..."}$ with $q$ chosen so two different strings hash equal. Suppose $h(\text{"cd"}) = h(\text{"ke"}) \pmod q$ by bad luck.

Hashes match → we must verify char-by-char.
Verification fails → we correctly reject. Why this matters: the hash is a filter, not a proof. Skipping verification would report a fake match.

Common Mistakes

Flashcards

Rabin-Karp core idea

Hash the pattern; compare it to a rolling hash of each text window in

O(1)

; verify on matches.

Why verify after a hash match?

Hash equality is necessary but not sufficient — distinct strings can collide, giving false positives.

Rolling update formula

H_{i+1} = ((H_i - T[i]\cdot b^{m-1})\cdot b + T[i+m]) \bmod q

Why multiply by

b

in the roll?

To shift every remaining digit up one place after dropping the leading character.

Expected vs worst time

Expected

O(n+m)

; worst case

O(nm)

when every window collides.

Role of the prime

q

Keeps numbers bounded and makes collision probability ~

1/q

; large prime → fewer false positives.

What must be precomputed for

O(1)

rolls?

b^{m-1} \bmod q

(the high-power weight).

How to avoid negative hash values?

Add

q

before final mod: ((x) % q + q) % q.

Recall Feynman: explain to a 12-year-old

Imagine every word is turned into a secret number using its letters, like a fingerprint. To find a word hidden inside a long sentence, you slide a window and compute its fingerprint. Computing a brand-new fingerprint each time is slow — but here's the magic: when you slide one letter over, you just erase the first letter's part and add the new letter's part, super fast. If two fingerprints match, you double-check the actual letters (because rarely two different words share a fingerprint). That double-check is your safety net.

Connections

Hashing — polynomial / modular hash foundations
Modular Arithmetic — why we use a prime $q$ and avoid negatives
Knuth-Morris-Pratt — guaranteed $O(n+m)$ (no collisions) via failure function
Z-Algorithm — another linear pattern matcher
String Hashing for Substring Comparison — same rolling idea for $O(1)$ range equality
Birthday Paradox — intuition for collision probability

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, Rabin-Karp ka core idea simple hai: har string ko ek number (hash) mein convert kar do, aur fir do strings compare karne ke bajaye sirf unke numbers compare karo — ye $O(1)$ mein ho jata hai. Hum text ke har length- $m$ window ka hash nikalte hain aur pattern ke hash se compare karte hain. Agar match nahi hua to seedha skip, agar match hua to character-by-character verify karte hain (kyunki kabhi-kabhi alag strings ka bhi same hash aa sakta hai — usko collision kehte hain).

Sabse important magic hai rolling hash. Har window ka hash dobara se scratch se nikalna slow hoga ( $O(m)$ har baar). Lekin jab window ek step aage slide karta hai, to hum bas teen kaam karte hain: purane pehle character ka contribution hatao ( $-T[i]b^{m-1}$ ), baaki sab ko shift karo ( $\times b$ ), aur naya last character add karo. Iss "Drop, Slide, Add" se update sirf $O(1)$ mein ho jata hai — yahi puri speed ka raaz hai.

Ek galti jo sab karte hain: hash match ho gaya to maan lete hain string match ho gayi. Galat! Hash sirf ek filter hai, proof nahi. Hamesha verify karo. Dusri common galti — subtraction ke baad negative value aa jati hai modular arithmetic mein, to ((x % q) + q) % q likho taaki value positive rahe. Aur $q$ hamesha bada prime lo (jaise $10^9+7$ ), warna collisions badh jayenge aur time $O(nm)$ ban jayega.

Overall, agar prime accha ho to expected time $O(n+m)$ aata hai, jo naive $O(nm)$ se bahut fast hai. Competitive programming mein ye technique substring comparison ke liye bhi kaam aati hai, isliye iska intuition pakka karna zaroori hai.

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

WHAT problem are we solving?

WHY hashing helps

HOW: building the hash from first principles

Deriving the rolling update

Complexity — WHY $O(n+m)$ expected

Worked Example 1 — tiny by hand

Worked Example 2 — a collision (steel-man)

Common Mistakes

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — String Algorithms

Connections