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

3.8.3 · D2 · Coding › String Algorithms › Rabin-Karp — rolling hash, O(n+m) expected

Hum ek hi sawaal ka jawab dhundhenge: jab letters ki ek window ek step right slide karti hai, toh kya hum bina har letter ko dobara add kiye uska naya "number" purane se nikaal sakte hain?

Step 1 — String ko ek single number mein badlo

KYA. String lo aur uske letters ko ek ordinary number ke digits ki tarah line up karo.

KYU. Do poore numbers compare karna ek single $O (1)$ operation hai; do strings ko letter-by-letter compare karna $O (m)$ hai. Agar hum kisi string ko fairly ek number mein squeeze kar sakein, toh matching fast ho jaati hai. == $O (1)$ == ka matlab hai "ek fixed amount of work, chahe string kitni bhi lambi ho."

PICTURE. Neeche diye figure mein string cab upar hai; uske neeche, har letter apne code $2, 0, 1$ mein drop hota hai. Dhyan do ki abhi tak hum unhe combine nahi kiya hai — yeh Step 2 mein hoga.

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

Codes ko simply add ( $2 + 0 + 1$ ) kyun nahi kar dete? Kyunki tab cab, bca, abc teeno $3$ denge — order kho jaayega. Hume position ka matter karna zaroori hai. Aur yahi kaam ek base karta hai.

Step 2 — Har position ko ek weight do (base $b$ )

KYA. Sabse left wale code ko sabse bada weight do aur right ki taraf $b^{0} = 1$ tak step down karo.

Base $b$ kyun, addition kyun nahi? Weights $b^{m - 1}, b^{m - 2}, \dots, b^{0}$ sab alag hain, isliye do letters ki positions swap hone se number badal jaata hai. Order ab encoded hai. Hum $b$ ko kam se kam alphabet size ke barabar choose karte hain taaki koi do "digit patterns" sasti jagah accidentally match na kar sakein.

PICTURE. Step 1 ke har code ko ab $b^{m - 1}, \dots, b^{0}$ height ke labelled pedestal par rakha gaya hai. Sabse uncha pedestal pehle letter ke neeche hai — leftmost letter "high digit" hai.

Step 3 — Number ko $mod q$ se chhota rakho

KYA. $H (s)$ compute karne ke baad, isse $q$ se modulo leke uske remainder se replace karo.

KYU. Lambi string ke liye $b^{m - 1}$ astronomically bada hota hai — machine word ke liye bahut bada. Sab kuch $mod q$ lena number ko $q - 1$ par cap kar deta hai aur saath hi +, −, × structure preserve karta hai (yeh modular arithmetic ki magic property hai: tum har step par reduce kar sakte ho). $q$ prime choose karna remainders ko evenly spread karta hai, taaki do alag strings ke ek hi remainder share karne ki probability lagbhag $1/ q$ ho (collisions ke liye Birthday Paradox ka intuition).

PICTURE. Ek tall bar (raw value) baar baar ek chhote box of width $q$ mein fold hoti hai; jo bacha woh remainder hai — wahi hash hum store karte hain.

Step 4 — Do paas-paas wali windows lagbhag poori overlap karti hain

KYA. Window $i$ ka number (letters $T [i .. i + m - 1]$ ) aur window $i + 1$ ka number (letters $T [i + 1.. i + m]$ ) ek ke upar ek likho aur un letters ko align karo jo share hote hain.

KYU. Poori speed-up ek single observation par tiki hai: do windows exactly ek letter each end par differ karti hain. Beech ka sab kuch identical hai — sirf uska weight badla hai. Agar hum us weight change ko sasti tarah express kar sakein, toh hum jeet jaate hain.

PICTURE. Overlapping block cyan mein shaded hai; dropped letter $T [i]$ left par amber hai, incoming letter $T [i + m]$ right par amber hai. Cyan block same letters hain — bas ek pedestal upar shift ho gaye.

Kuch derive karne se pehle dono numbers ko naam dete hain:

Step 5 — Drop, Slide, Add (derivation)

Hum $H_{i}$ ko teen moves mein $H_{i + 1}$ mein convert karte hain. Har move ek arithmetic operation hai, isliye total $O (1)$ hai.

Move 1 — DROP. Leading letter ka contribution $T [i] b^{m - 1}$ hata do. $H_{i} - T [i] b^{m - 1} = T [i + 1] b^{m - 2} + \dots + T [i + m - 1] b^{0}$ Kyun: purana high digit sirf purani window ka tha. Yahan $T [i]$ woh code hai jo hum evict kar rahe hain aur $b^{m - 1}$ woh pedestal hai jis par yeh khada tha.

Move 2 — SLIDE. Baaki bache ko $b$ se multiply karo. $(H_{i} - T [i] b^{m - 1}) \cdot b = T [i + 1] b^{m - 1} + \dots + T [i + m - 1] b^{1}$ Kyun: $b$ se multiply karna har weight ko $b^{k} \to b^{k + 1}$ kar deta hai — exactly wahi "weights ek upar gaye" wali baat Step 4 se. Yeh shift hai, ek single multiply se saare shared letters par ek saath.

Move 3 — ADD. Naye trailing letter ko weight $b^{0}$ par daalo. $(H_{i} - T [i] b^{m - 1}) \cdot b + T [i + m] = H_{i + 1}$ Kyun: incoming letter $T [i + m]$ naya low digit hai; $b^{0} = 1$ hai isliye yeh simply add ho jaata hai.

PICTURE. Teen panels, left→right: amber leading pedestal knock off hoti hai (Drop); cyan block ek level upar uthti hai (Slide); right par ground level par ek naya amber block aata hai (Add).

Step 6 — Degenerate cases (reader ko edge se girne mat do)

Case A — $m = 1$ (single-letter pattern). Tab $b^{m - 1} = b^{0} = 1$ . Drop $T [i]$ hata deta hai, slide $b$ se multiply karta hai, add $T [i + m]$ deta hai; algebra collapse hokar $H_{i + 1} = T [i + 1]$ ban jaata hai, jo sirf ek visible letter ka code hai. Sahi hai.

Case B — subtraction negative ho jaaye. $H_{i} - T [i] b^{m - 1}$ negative ho sakta hai $mod q$ reductions ke baad, kyunki ek remainder us cheez se chhota ho sakta hai jo hum subtract kar rahe hain. $H_{i + 1} = (((H_{i} - T [i] \cdot P_{high}) mod q + q) mod q \cdot b + T [i + m]) mod q$ $+ q$ kyun: final $mod$ se pehle ek pura $q$ add karna kisi bhi negative ko $[0, q)$ mein wapas le aata hai bina residue badlaye.

Case C — collision (hashes equal, letters differ). Number ek fingerprint hai, proof nahi. Jab do windows ek hash share karein tab bhi hum letters compare karte hain. Verification $O (m)$ cost karti hai lekin sirf lagbhag $1/ q$ baar hoti hai — filter-then-check discipline ke liye String Hashing for Substring Comparison dekho.

PICTURE. Left: $m = 1$ window ek single pedestal tak shrink ho gayi. Middle: ek negative bar $+ q$ arrow se valid box mein push ho rahi hai. Right: ek equal fingerprint share karte do alag words, beech mein amber "VERIFY" stamp.

Step 7 — Ek number jo actually roll karta hai (worked check)

$P = "ab"$ ko $T = "aab"$ mein search karo, base $b = 26$ , prime $q = 101$ , codes $a = 0, b = 1$ .

$h (P) = 0 \cdot 26 + 1 = 1$ .
Window 0 "aa": $0 \cdot 26 + 0 = 0$ . Kyunki $0 \neq = 1$ , skip — ek comparison, koi letter check nahi.
Precompute $P_{high} = b^{m - 1} = 2 6^{1} = 26$ .
Window 1 "ab" par roll karo: $H_{1} = (H_{0} 0 - T [0] = a 0 \cdot P_{high} 26) \cdot slide 26 + T [2] = b 1 = 1.$
$H_{1} = 1 = h (P)$ → verify → "ab" == "ab" ✓ → index $1$ par match.

PICTURE. Tape a a b jisme window positions $0 - 1$ se $1 - 2$ par jump karti hai; upar hash labels $0 \to 1$ , aur doosri window par amber "MATCH @1" flag.

Ek-picture summary

Upar ki poori cheez ek single diagram mein: string → codes → weighted sum → fold mod $q$ → aur Drop/Slide/Add loop jo har agla window free bana deta hai.

Recall Feynman: poora walkthrough apne words mein batao

Socho ek word digits ki tarah likha hai, jaise cab ko $2, 0, 1$ mein badalna. Un digits se ek number banana ke liye, main unhe ek real number ki tarah stack karta hoon: left digit sabse unche tower par (sabse bada weight) aur right digit ground floor par. Bade numbers bahut bade ho jaate hain, isliye main value ko baar baar size $q$ ke chhote box mein fold karta hoon aur sirf jo bacha — woh remainder — woh word ki fingerprint hai. Ab main ek lambi sentence mein ek window slide karti hoon. Do paas-paas windows apne almost saare letters share karti hain — sirf front wala nikalta hai aur ek naya join karta hai. Toh fingerprint dobara build karne ki bajaye, main teen quick moves karta hoon: jaane wale letter ko uske unche tower se knock karo, baaki sab ko ek floor upar uthao (base se multiply karo), aur naye letter ko ground floor par daalo. Teen operations, ho gaya. Agar fingerprint pattern ki se match kare, tab bhi main real letters check karta hoon — kyunki kabhi kabhi do alag words ek fingerprint share kar lete hain. Bas yahi poora trick hai.

Recall Quick self-test

Roll mein $b$ se multiply kyun karte hain? ::: Har remaining letter ka weight $b^{k}$ se $b^{k + 1}$ karne ke liye — shared block ek place upar slide karta hai. Pehle $T [i] b^{m - 1}$ subtract kyun karte hain? ::: Jaane wale letter ko evict karne ke liye, jo purani window ke sabse bade weight par baitha tha. Kya precompute karna padta hai? ::: $P_{high} = b^{m - 1} mod q$ , ek baar, warna roll $O (1)$ nahi rehta. Hash match ke baad bhi verify kyun karte hain? ::: Hash ek filter hai; alag strings collide kar sakti hain (~ $1/ q$ chance). $q$ chhota ho toh kya break hota hai? ::: Constant collisions → har jagah verify → $O (nm)$ .

Connections

Parent topic — full Rabin-Karp note
Hashing — fingerprint idea in general
Modular Arithmetic — kyun har step par reduce karna legal hai, aur $+ q$ fix
String Hashing for Substring Comparison — same roll $O (1)$ range equality ke liye
Birthday Paradox — collisions ~ $1/ q$ kyun hote hain
Knuth-Morris-Pratt, Z-Algorithm — collision-free linear alternatives