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

3.8.3 · Coding › String Algorithms

Hum KON SA problem solve kar rahe hain?

Ek text $T$ diya hai jiskii length $n$ hai aur ek pattern $P$ diya hai jiskii length $m$ hai; hume har woh position $i$ dhundni hai jahan $P$ occur karta ho $T$ mein (yaani $T [i .. i + m - 1] = P$ ).

Naive approach har $n - m + 1$ windows ko $m$ characters compare karke check karta hai → worst case $O (nm)$ . Rabin-Karp ka target hai $O (n + m)$ expected.

Hashing KYUN help karta hai

Agar $h (P) \neq = h (window)$ , toh strings definitely alag hain — turant skip karo. Agar $h (P) = h (window)$ , toh woh probably equal hain, isliye hum verify karte hain. Equal strings ka hash hamesha equal hota hai, isliye hum koi match miss nahi karte. Ek hi risk hai false positive (collision), jisme extra $O (m)$ check lagta hai.

KAISE: hash ko first principles se build karna

Ek string ko base $b$ mein ek number ki tarah treat karo (digits ki tarah socho). Ek string $s$ jo length $m$ ki hai, jiske character codes $s_{0}, s_{1}, \dots, s_{m - 1}$ hain:

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

Rolling update derive karna

Hamare paas window $T [i .. i + m - 1]$ ka hash hai:

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

Hume $H_{i + 1}$ chahiye window $T [i + 1.. i + m]$ ke liye. Teen operations:

Remove karo leading char $T [i]$ ko, jo $T [i] b^{m - 1}$ contribute karta hai.
Shift left (multiply by $b$ ): baaki har term ka exponent 1 badh jaata hai.
Add karo naya trailing char $T [i + m] b^{0}$ .

Toh:

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

Yeh step KYUN? Subtract karne se purana high-order digit khatam hota hai; $b$ se multiply karne par sab shift ho jaate hain; add karne se naya low-order digit insert hota hai. Sab $O (1)$ — yahi poora speedup hai.

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

Complexity — $O (n + m)$ expected KYUN hai

$h (P)$ aur $h (T [0.. m - 1])$ precompute karo: $O (m)$ .
$n - m + 1$ windows par slide karo, har update $O (1)$ : $O (n)$ .
Sirf hash matches par verify karo. Ek acche prime $q$ se, spurious match ki probability roughly $1/ q$ hoti hai, isliye expected verification cost tiny hai → total $O (n + m)$ expected.
Worst case $O (nm)$ (har window collide kare, jaise small $q$ ke saath adversarial input).

Worked Example 1 — chhota sa haath se

$P = "ab"$ dhundho $T = "aab"$ mein. Base $b = 26$ , $q = 101$ , code $a = 0, b = 1$ lo.

$h (P) = 0 \cdot 26 + 1 = 1$ .
Window 0 = "aa": $0 \cdot 26 + 0 = 0$ . Kyun? digits hain $a = 0, a = 0$ . $0 \neq = 1$ → skip.
Roll karo window 1 = "ab" par: $P_{high} = b^{1} = 26$ . $H_{1} = (0 - T [0] \cdot 26) \cdot 26 + T [2] = (0 - 0) \cdot 26 + 1 = 1$ . Kyun? leading 'a'(=0) remove hua, shift hua, 'b'(=1) add hua. $h (P) = 1$ se match → verify → "ab"=="ab" ✓. Index 1 par match.

Worked Example 2 — ek collision (steel-man)

$T = "xy"$ , $P = "..."$ jisme $q$ aise choose kiya ki do alag strings ka hash equal ho jaaye. Maano $h ("cd") = h ("ke") (mod q)$ bad luck se.

Hashes match karte hain → hume zaroor char-by-char verify karna hai.
Verification fail hoti hai → hum correctly reject karte hain. Yeh kyun matter karta hai: hash ek filter hai, proof nahi. Verification skip karna fake match report karega.

Common Mistakes

Flashcards

Rabin-Karp ki core idea

Pattern ko hash karo; usse har text window ke rolling hash se

O (1)

mein compare karo; matches par verify karo.

Hash match ke baad verify kyun karte hain?

Hash equality necessary hai par sufficient nahi — alag strings collide ho sakti hain, jo false positives deti hain.

Rolling update formula

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

Roll mein

b

se multiply KYUN karte hain?

Leading character drop karne ke baad baaki har digit ko ek place upar shift karne ke liye.

Expected vs worst time

Expected

O (n + m)

; worst case

O (nm)

jab har window collide kare.

Prime

q

ka role

Numbers bounded rakhta hai aur collision probability ~

1/ q

banata hai; bada prime → kam false positives.

O (1)

rolls ke liye kya precompute karna padta hai?

b^{m - 1} mod q

(high-power weight).

Negative hash values se kaise bachein?

Final mod se pehle

q

add karo: ((x) % q + q) % q.

Recall Feynman: ek 12-saal ke bacche ko explain karo

Socho har word ko uske letters se ek secret number mein convert kiya jaata hai, jaise ek fingerprint. Ek lambe sentence mein koi word dhundhne ke liye, tum ek window slide karte ho aur uska fingerprint compute karte ho. Har baar bilkul naya fingerprint compute karna slow hai — par yahan magic yeh hai: jab tum ek letter aage slide karte ho, tum bas pehle letter ka hissa mitaate ho aur naye letter ka hissa add karte ho, bahut fast. Agar do fingerprints match karein, tum actual letters double-check karte ho (kyunki kabhi-kabhi do alag words ka fingerprint same hota hai). Woh double-check tumhara safety net hai.

Connections

Hashing — polynomial / modular hash ke foundations
Modular Arithmetic — kyun hum prime $q$ use karte hain aur negatives se bachte hain
Knuth-Morris-Pratt — guaranteed $O (n + m)$ (koi collision nahi) failure function ke zariye
Z-Algorithm — ek aur linear pattern matcher
String Hashing for Substring Comparison — same rolling idea $O (1)$ range equality ke liye
Birthday Paradox — collision probability ka intuition