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

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

Ye bank parent topic ke ideas drill karta hai. Neeche kuch bhi heavy arithmetic nahi hai — woh D3/D4 mein hain.

Is page par use hone wala Notation

Traps se pehle, har symbol ko pin down karte hain taaki neeche koi line kuch undefined use na kare. Picture yeh hai: text boxes ki ek row hai, aur ek window width $m$ ka ek lal frame hai jo ek box ek time rightward slide karta hai.

Agla figure un teeno moves ko dikhata hai jo frame par act karte hain jab woh box $i$ se box $i + 1$ par step karta hai.

True ya false — justify karo

Hash match prove karta hai ki pattern us window par occur karta hai

False. Hash ek filter hai, proof nahi — do alag strings collide hokar same value de sakti hain, isliye match ka matlab sirf "probably equal hai, ja ke verify karo" hota hai.

Hash mismatch prove karta hai ki pattern wahan occur nahi karta

True. Equal strings hamesha equal hash karti hain, isliye unequal hashes guarantee karte hain ki strings differ karti hain — yahi wajah hai ki hum instantly skip kar sakte hain aur koi real match kabhi miss nahi hota.

Rabin-Karp worst case mein

O (n + m)

hai

False. Yeh

O (n + m)

expected hai; worst case

O (nm)

hai jab har window ka hash pattern se collide karta hai, har baar full verification force karta hai.

Bada prime

q

use karna sirf correctness ke liye help kar sakta hai, kabhi hurt nahi karta

Correctness ke liye True (verification hamesha correctness guarantee karta hai). Lekin practice mein yeh free nahi hai: itna bada

q

ki hashes machine word se overflow ho jaayein, slower big-integer ya 128-bit arithmetic force karta hai, isliye har operation zyada costly ho jaati hai chahe collisions girain — ek large prime chuno jo comfortably machine word mein fit ho.

Rolling update har slide par poora hash recompute karta hai

False. Poora point yahi hai ki woh nahi karta — woh

H_{i + 1} = (b (H_{i} - T [i] P_{high}) + T [i + m]) mod q

se "drop, slide, add" karta hai

O (1)

mein, modular operations ke zariye pichhle window ke hash ko reuse karta hai.

Agar

q

prime hai, toh collisions impossible ho jaate hain

False. Prime

q

sirf collisions reduce karta hai; finite hash values hain (

q

jinke) aur infinite strings hain, isliye collisions phir bhi exist karni chahiye (pigeonhole).

Base

b

ko alphabet size se chhota choose karna theek hai

False. Agar

b

distinct characters ki sankhya se chhota hai, toh do alag characters "same digit" ki tarah act kar sakte hain aur systematic collisions cause kar sakte hain —

b \geq

alphabet size chuno.

Rabin-Karp ko shuru hone se pehle pattern length

m

chahiye

True. Window size

m

par fixed hai, aur

P_{high} = b^{m - 1} mod q

aur pattern hash dono

m

par depend karte hain; known length ke bina koi meaningful rolling window nahi hai.

Knuth-Morris-Pratt aur Rabin-Karp ka same guarantee hai

False. KMP guaranteed

O (n + m)

hai (koi randomness nahi, koi collision nahi), jabki Rabin-Karp sirf expected

O (n + m)

hai aur adversarially

O (nm)

tak degrade ho sakta hai.

Error dhundho

"Kyunki hashes match hue, hum match report karte hain aur aage badhte hain — verification time ki barbaadi hai."

Error verification skip karna hai: alag strings collide ho sakti hain, isliye yeh false positives report karta hai. Verification woh

O (m)

safety net hai jo algorithm ko correct rakhta hai.

"Hum

H_{i} - T [i] \cdot P_{high}

compute karte hain aur mod

q

lete hain; result

[0, q)

mein hai."

Subtraction mod se pehle negative ho sakta hai, aur kai languages mein negative number par % negative hota hai. Fix: ((H - x) % q + q) % q taaki yeh

[0, q)

mein force ho.

"Numbers ko chhota aur fast rakhne ke liye, hum

q = 13

choose karte hain."

Chhota

q

frequent collisions produce karta hai, isliye verification almost har window par fire karta hai, running time ko

O (nm)

ki taraf le jaata hai. Ek large prime jaise

1 0^{9} + 7

use karo.

"Loop ke andar hum har step par pow(b, m-1) % q compute karte hain taaki code simple rahe."

Har iteration mein

b^{m - 1}

recompute karna har roll ko

O (lo g m)

O (m)

bana deta hai,

O (1)

update ko destroy kar deta hai. Loop se pehle ek baar

P_{high} = b^{m - 1} mod q

precompute karo.

"Hamara hash

s_{0} + s_{1} + \dots + s_{m - 1}

hai — character codes ka sum. Simple aur collision-free."

Plain sum position-blind hai: "ab" aur "ba" identically hash hote hain, isliye yeh massively collide karta hai. Polynomial base-

b

weighting isi liye exist karta hai taaki position matter kare.

"Hum

q = 1 0^{9} + 7

ke saath single hash use karte hain, isliye hum safely character check skip kar sakte hain."

Bada prime bhi nonzero collision chance (~

1/ q

) chhodta hai; kai windows par ek false positive ho sakta hai. Correctness requires verification regardless of

q

ki size — Birthday Paradox dekho.

"Rolling right

T [i + m]

add karta hai aur

T [i]

drop karta hai, isliye operations ka order matter nahi karta."

Order matter karta hai: pehle tumhe leading term ki current weight drop karni hai (

T [i] \cdot P_{high}

, jahaan

P_{high} = b^{m - 1}

) phir

b

se multiply karo, phir naya low digit add karo. Inhe galat order mein karne se digit positions corrupt ho jaate hain.

Why questions

Roll ke dauran hum sirf do characters swap karne ki jagah

b

se multiply kyun karte hain?

Kyunki har character ka contribution uski position se weighted hota hai (

b^{m - 1}

se lekar

b^{0}

tak); window slide karna har remaining character ko ek jagah upar shift karta hai, aur poore hash ko

b

se multiply karna woh saari shifts ek saath perform karta hai.

Hash ko kisi bhi large number ki jagah prime modulo kyun lete hain?

Prime

q

hash values ko zyada uniformly spread karta hai aur

b

ke saath common factors avoid karta hai jo kai strings ko same residue mein collapse kar dete, collision rate ko

1/ q

ke aas paas rakhta hai.

Hash mismatch trustworthy kyun hai lekin hash match nahi?

Equal strings equal hashes produce karne par forced hoti hain (function deterministic hai), isliye mismatch conclusive hai; lekin kai strings har hash value par map hoti hain, isliye match sirf suggestive hai aur check karna zaroori hai.

Rabin-Karp sirf "expected" linear kyun hai guaranteed nahi?

Verification cost depend karta hai kitne spurious hash matches hote hain, jo ek probabilistic quantity hai (har window par

\approx 1/ q

); ek adversary jo collisions engineer karta hai woh ise

O (nm)

bana sakta hai.

Rabin-Karp naturally multiple patterns of same length search karne ke liye kyun extend hota hai?

Tum har pattern ke liye hash precompute kar sakte ho aur unhe ek set mein store kar sakte ho; har text window ka hash ek baar

O (1)

mein lookup hota hai, isliye kai patterns ek se thoda zyada cost karte hain — kuch aisa jo Knuth-Morris-Pratt utne cheaply share nahi karta.

String Hashing for Substring Comparison same rolling idea kyun reuse karta hai?

Dono base-

b

polynomial hash par rely karte hain taaki kisi bhi substring ka hash prefix hashes se derive kiya ja sake, jisse tum do ranges ko

O (1)

mein compare kar sako — rolling window sirf sliding special case hai.

Agar

m

chhota hai toh hum sirf naive

O (nm)

compare kyun nahi use kar sakte?

Tum kar sakte ho, aur yeh aksar theek hota hai — Rabin-Karp ka advantage

m

ke saath aur patterns ki sankhya ke saath badhta hai; ek single short pattern ke liye hashing ke constant factors payoff nahi de sakte.

Edge cases

Jab pattern text se lamba ho (

m > n

) toh kya hota hai?

Test karne ke liye koi length-

m

windows nahi hain, isliye algorithm immediately zero matches report karta hai —

n - m + 1

windows ka loop simply run nahi hota.

Agar pattern aur text equal length ke hain (

m = n

Exactly ek window hai (poora text); hum do hashes ek baar compare karte hain aur match hone par verify karte hain — bilkul bhi rolling nahi hoti.

Empty pattern (

m = 0

) ka hash kya hai?

Polynomial sum empty hai, hash

0

deta hai; conventionally empty string har position par "match" karti hai, isliye yeh case usually roll ke bajaye special guard ke roop mein handle hota hai.

Single-character pattern (

m = 1

) ke saath kya hota hai?

P_{high} = b^{0} = 1

aur har hash sirf character ka code mod

q

hai; roll degenerate ho jaata hai ek character compare karne mein, essentially naive scan.

Algorithm kaise behave karta hai jab

T

ka har character identical ho (jaise "aaaa") aur

P

"aa" ho?

Har window ka same hash hai aur genuinely match karta hai, isliye verification har baar succeed karta hai — yeh legitimate work hai, collision nahi, aur yeh

O (nm)

tabhi hai jab answer set itself itna bada ho.

Agar do alag strings collide karein lekin koi bhi pattern nahi hai?

Koi farak nahi padta — hum sirf har window ke hash ko pattern ke hash se compare karte hain, isliye do non-pattern strings ke beech collisions kabhi observe nahi hote aur kuch cost nahi karte.

Kya hash of

0

matlab hai ki string empty hai?

Nahi. Zero ek non-empty string ke liye perfectly valid hash hai (jaise "aa" code

a = 0

ke saath

0

hash karta hai); numeric value apne aap mein koi "emptiness" meaning nahi carry karta.

Recall Har trap ka one-sentence summary

Baar-baar milne wala lesson: hash filter karta hai, verification decide karta hai — mismatches conclusive hain, matches nahi, $q$ correctness nahi speed tune karta hai, aur har degenerate length ( $m > n$ , $m = n$ , $m = 1$ , $m = 0$ ) ko rolling loop par trust karne se pehle handle karna zaroori hai.

Connections

Parent topic — full derivation
Hashing — collisions isliye hain ki matches ko verify karna kyun zaroori hai
Modular Arithmetic — negative-value trap yahan rehta hai
Knuth-Morris-Pratt — guaranteed vs expected linearity
Z-Algorithm — comparison ke liye ek aur linear matcher
String Hashing for Substring Comparison — same rolling idea generalized
Birthday Paradox — kyun collisions tumhare guess se pehle appear hote hain