3.8.3 · D1Rabin-Karp — rolling hash, O(n+m) expected
Rabin-Karp text ke har chunk ko ek single number ("fingerprint") mein badal deta hai, taaki do chunks ko compare karna sirf do numbers compare karna ho — instant. Isse puri long text mein fast banane ke liye, hum fingerprint aise banate hain ki window ko ek step slide karna sirf kuch arithmetic operations mein number update kar de — har baar har character dobara padhne ki zaroorat nahi.
Ye page assume karta hai ki tumne pehle kuch nahi dekha. Parent note mein use kiya gaya har letter, subscript, aur squiggle yahan unpack kiya gaya hai, ek aisi order mein jahan har idea sirf pehle wale ideas pe depend karta hai.
Ek string bas characters ki ek ordered row hai — letters, digits, symbols — jo left se right rakhe hote hain. Hum ise s
Ek string ko boxes ki row ki tarah socho, jisme har box ek character rakhta hai:
Parent note mein s 0 , s 1 , … , s m − 1
Definition Index aur subscript notations 0 , s 1 , … index hai — character ki position , 0 s 0 s 1
Figure dekhо: red box s 0
Definition Character codeComputers letter "a" directly store nahi kar sakte — woh uske liye ek number store karte hain. Woh number character ka code hai. Parent ke chhote example mein codes haath se choose kiye gaye hain: a = 0 b = 1 'a' ka code 97
Ye topic ise kyun chahta hai: hum abhi ek poori string ko ek bada number treat karne wale hain. Iske liye, pehle har character ko ek number hona chahiye. Code woh pehla translation hai.
m n n text T m pattern P
Kyunki P m P [ 0 ] , P [ 1 ] , … , P [ m − 1 ] m − 1 m 0
Ye topic ise kyun chahta hai: note mein har cost (O ( nm ) O ( n + m ) m n
O ( ⋅ ) O ( something ) rough count hai, sirf woh rakhte hain jo matter karta hai jab input bada ho. O ( m ) m O ( 1 )
O ( nm ) O ( n + m ) O ( nm ) n m n × m O ( n + m ) n = 1000 , m = 100 100 , 000 1 , 100
Ye topic ise kyun chahta hai: poora selling point ek speed claim hai. Jaane bina ki O ( n + m ) matlab kya hai, "expected O ( n + m )
T [ i .. i + m − 1 ] window text ka ek slice hai jo exactly m T [ i .. i + m − 1 ] T i i + m − 1 i m i + m − 1
Sliding ka matlab hai: window ko ek box right mein move karo, toh i i + 1
Figure mein, red character woh hai jo slide karte waqt enter kar raha hai; left pe greyed wala leave kar raha hai. Yahi "ek jaata hai, ek aata hai" wali picture rolling update ko possible banati hai — sirf do characters change hote hain.
Ye topic ise kyun chahta hai: n − m + 1 0 , 1 , …
Hashing se pehle, tumhe feel karna chahiye ki ordinary numbers kaise bante hain.
b 10 2 ⋅ 1 0 2 + 3 ⋅ 1 0 1 + 7 ⋅ 1 0 0 . b b = 10 power se multiply kiya jaata hai uski jagah ke hisaab se. Sabse left wala digit sabse bada weight carry karta hai.
Definition Exponent / powerb k b k b k b 0 = 1 1 0 2 = 100 1 0 1 = 10 1 0 0 = 1
Intuition String ko base-b b b = 26
Ye topic ise kyun chahta hai: hash formula
H ( s ) = s 0 b m − 1 + s 1 b m − 2 + ⋯ + s m − 1 b 0 exactly "237" ka place-value formula hai, bas character codes digits ki jagah hain aur base b
Upar wala fingerprint number ek lambi string ke liye bahut bada ho sakta hai. Hum ise remainder se kabu karte hain.
a mod q a mod q remainder hai jo a q 17 mod 5 = 2 17 = 3 ⋅ 5 + 2 { 0 , 1 , … , q − 1 }
Intuition Ghadi wali pictureEk ghadi mod 12 12 0 q q mod q q
q q prime (sirf 1 large (jaise 1 0 9 + 7 Modular Arithmetic dekhо.
Common mistake Code mein remainders negative kyun ja sakte hainJab hum roll ke dauran subtract karte hain, toh H i − T [ i ] ⋅ P high 0 − 3 mod 12 9 − 3 ((x) % q + q) % q — use wapas ghadi ke face par le aata hai.
Ye topic ise kyun chahta hai: har hash ( mod q ) q 1/ q Hashing , Birthday Paradox .
Ab parent ke formulas ke symbols sab earn ho chuke hain:
P high = b m − 1 mod q subtract karna padta hai, aur woh weight hamesha b m − 1 b m − 1 O ( 1 ) ek baar compute karo, hamesha ke liye reuse karo.
Ye topic ise kyun chahta hai: P high
Ek collision tab hoti hai jab do alag strings ek hi fingerprint produce karti hain. Kyunki hum infinitely many strings ko sirf q 1/ q
Intuition Hum phir bhi character-by-character verify kyun karte hainEqual strings ke hashes hamesha equal hote hain — toh hashes ka mismatch matlab "definitely equal nahi," jo hum trust karke instantly skip kar sakte hain. Lekin equal hashes ka matlab sirf "probably equal" hota hai. Toh hash hit par hum ek O ( m ) filter hai, proof nahi .
Ye topic ise kyun chahta hai: isliye algorithm expected O ( n + m ) Birthday Paradox dekhо.
Index and subscript s0 s1
Precomputed b to m minus 1
s 2 Character ki position, 0 s 2 teesra box hai.
n m n T m P
O ( 1 ) Input size se independent, steps ki ek fixed sankhya — constant time.
"504" ko base-10 5 ⋅ 1 0 2 + 0 ⋅ 1 0 1 + 4 ⋅ 1 0 0
Kisi bhi base b b 0 1
17 mod 5 2 17 = 3 ⋅ 5 + 2
q Fingerprints evenly spread karne ke liye aur collisions rare banane ke liye (~1/ q
Code mein modular result negative kyun ja sakta hai, aur fix kya hai? Subtraction 0 ((x) % q + q) % q.
Length n m n − m + 1
Collision kya hai, aur hum panic kyun nahi karte? Do alag strings ek hash share karti hain; hum ise har hash hit par ek O ( m )
b m − 1 mod q Yeh leaving character ka weight hai, har slide mein chahiye; ise ek baar compute karna roll ko O ( 1 )
Hashing — polynomial/modular fingerprint idea puri tarah seModular Arithmetic — ghadi, remainders, aur q Birthday Paradox — collisions actually kitni likely hainString Hashing for Substring Comparison — wahi rolling hash range equality ke liye reuse kiya gayaKnuth-Morris-Pratt — ek collision-free linear matcher (contrast)Z-Algorithm — ek aur linear pattern matcher (contrast)