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

KYA: hum $H$ ko term by term expand karte hain. KYUN: sabse baayi taraf wala character most significant digit hai, isliye woh $b$ ki sabse zyada power se multiply hota hai. $H(\text{cat})=2\cdot 26^2+0\cdot 26^1+19\cdot 26^0.$ Compute karo: $2\cdot 676=1352$, plus $0$, plus $19=1371$. Pehla character c weight $b^2=676$ carry karta hai.

Conclude: strings definitely different hain. Equal strings hamesha equal hashes produce karti hain, isliye unequal hashes se unequal strings zaroori hain. Karo: is window ko instantly skip karo — koi bhi character check zaroori nahi hai. (Contrast: hash match ka matlab sirf "probably equal" hai, isliye usse verification ki zaroorat hoti hai.)

L1.1 se raw value $1371$ hai. KYUN mod: hum ise chhota aur bounded rakhte hain. $1371=13\cdot 101+58$, kyunki $13\cdot 101=1313$ aur $1371-1313=58$. $H(\text{cat})\mathrm{mod}101=58.$

Precompute $P_{\text{high}}=b^{m-1}\mathrm{mod}q=26^2\mathrm{mod}101=676\mathrm{mod}101$. Kyunki $676=6\cdot 101+70$, $P_{\text{high}}=70$. Drop leading c$=2$: $58-2\cdot 70=58-140=-82$. Non-negative rakho: $(-82\mathrm{mod}101)=101-82=19$. Slide ($\times b$) aur Add trailing s$=18$: $(19\cdot 26+18)\mathrm{mod}101=(494+18)\mathrm{mod}101=512\mathrm{mod}101$. $512=5\cdot 101+7$, isliye $H_1=7$. Direct formula se check karo: $H(\text{ats})=0\cdot 676+19\cdot 26+18=494+18=512$; $512\mathrm{mod}101=7$. ✓ Roll aur direct computation agree karte hain — yahi poori baat hai.

$h(P)=0\cdot 26+1=1$. Window 0 "aa" $=0\cdot 26+0=0\ne 1$ → skip. Window 1 "ab" pe roll karo: $P_{\text{high}}=26^1\mathrm{mod}101=26$. $H_1=((0-0\cdot 26)\cdot 26+1)\mathrm{mod}101=1$. $h(P)$ se match karta hai → verify karo → "ab"=="ab" ✓. Match at index 1.

$H(\text{ac})=(0\cdot 26+2)\mathrm{mod}3=2$. $H(\text{ba})=(1\cdot 26+0)\mathrm{mod}3=26\mathrm{mod}3=2$. Woh collide karte hain ($2=2$) bhaale strings alag hain. Consequence: chhote $q$ ke saath, bahut saari windows equal hashes produce karti hain, isliye hum $O(m)$ verification baar baar chalate hain → "expected $O(n+m)$" worst case $O(nm)$ ki taraf collapse ho jaata hai. Isliye hum $10^9+7$ jaisa bada prime choose karte hain. Dekho Modular Arithmetic aur Birthday Paradox.

KYUN yeh tool: expected count $=$ (number of trials) $\times$ (per-trial probability), yeh linearity-of-expectation shortcut hai. $\mathbb{E}[\text{spurious}]\approx N\cdot \frac{1}{q}=\frac{10^6}{10^9+7}\approx 10^{-3}.$ Lagbhag har hazaar searches mein se sirf ek mein ek bhi wasted verification hoti hai — negligible. Isliye total expected cost $O(n+m)$ rehta hai.

Lo $T=\text{"aaaa...a"}$ ($n$ copies) aur $P=\text{"aaa...a"}$ ($m$ copies). Har window $P$ ke equal hai, isliye har hash match karta hai aur har window ek full $O(m)$ verification trigger karti hai. Total $=(n-m+1)\cdot O(m)=O(nm)$. Note karo yeh ek genuine-match worst case hai; ek adversarial collision worst case ki jagah ek known small $q$ use karta hai aur aisi alag windows craft karta hai jo sab $h(P)$ pe hash karti hain. Dono average-case bound ko defeat karte hain. Isliye Knuth-Morris-Pratt (guaranteed $O(n+m)$) prefer kiya jaata hai jab adversaries possible hon.

KYUN independence multiply karta hai: do independent events dono tab hote hain jab probability product ke equal hoti hai. Combined rate $\approx \frac{1}{q_1}\cdot \frac{1}{q_2}=\frac{1}{101\cdot 103}=\frac{1}{10403}$. Ek single hash mod $10^4$ deta hai $\frac{1}{10000}$. Toh do chhote primes ($101,103$) already ek modulus of $10^4$ se better hain: $\frac{1}{10403}<\frac{1}{10000}$. Lesson: do independent moduli apni protection multiply karte hain, isliye double hashing itna strong hai. Dekho String Hashing for Substring Comparison.

$h(P)=0\cdot 26+1=1$. $P_{\text{high}}=26$. $T$ ke codes: $b,a,b,a,b=1,0,1,0,1$.

• Window 0 "ba": $1\cdot 26+0=26$. $26\mathrm{mod}101=26\ne 1$ → skip.
• Roll → Window 1 "ab": drop b$=1$: $26-1\cdot 26=0$; slide+add b$=1$: $(0\cdot 26+1)=1$. $=1$ → verify "ab" ✓. Match at 1.
• Roll → Window 2 "ba": drop a$=0$: $1-0=1$; slide+add a$=0$: $(1\cdot 26+0)=26$. $\ne 1$ → skip.
• Roll → Window 3 "ab": drop b$=1$: $26-26=0$; slide+add b$=1$: $(0+1)=1$. $=1$ → verify ✓. Match at 3. Matches: indices 1 aur 3. (Direct check: babab[1..2]=ab, [3..4]=ab. ✓)

Design:

1. Double hashing use karo: do random large primes $q_1,q_2\approx 10^9$, random bases $b_1,b_2$. Kyun: combined collision rate $\approx q_1^{-1}{q}_2^{-1}\approx 10^{-18}$ — yahan tak ki ek crafted adversary random bases predict nahi kar sakta, isliye L3.3 ka collision attack fail ho jaata hai.
2. Har hash ke liye $P_{\text{high}}=b^{m-1}\mathrm{mod}q$ ek baar precompute karo. Kyun: loop ke andar recomputing karne se har roll $O(\log m)$ ho jaata hai aur speedup khatam ho jaata hai (scale pe L2 precompute mistake).
3. Subtraction ko ((x)%q+q)%q se guard karo. Kyun: negative-hash corruption rokta hai (L2 trap).
4. (Double) hash hit pe char-by-char verify karna jaari rakho. Kyun: correctness ko exact rakhta hai, aur double hashing ke saath verifications essentially sirf true matches pe hoti hain, isliye expected time $O(n+m)$ rehta hai.
5. Fallback: agar guaranteed worst-case $O(n+m)$ mandate hai (jaise hard real-time), toh Knuth-Morris-Pratt ya Z-Algorithm pe switch karo, jinhe koi randomness ki zaroorat nahi.

Likho $H_i={\sum }_{k=0}^{m-1}T[i+k]b^{m-1-k}$. Leading term hai $T[i]b^{m-1}$. Drop: $H_i-T[i]b^{m-1}={\sum }_{k=1}^{m-1}T[i+k]b^{m-1-k}$. Slide ($\times b$): ${\sum }_{k=1}^{m-1}T[i+k]b^{m-k}$. $j=k-1$ se re-index karo: ${\sum }_{j=0}^{m-2}T[i+1+j]b^{m-1-j}$ — yeh $T[i+\mathrm{1..}i+m-1]$ ka hash hai lekin uska aakhri character missing hai aur har weight ek power zyada high hai... precisely, yeh $H(T[i+\mathrm{1..}i+m])$ ke pehle $m-1$ terms ke barabar hai. Add $T[i+m]b^0$: final low-order digit fill karta hai, deta hai ${\sum }_{j=0}^{m-1}T[i+1+j]b^{m-1-j}=H(T[i+\mathrm{1..}i+m])$. ∎ Mod validity: addition, subtraction, aur multiplication sab "$\mathrm{mod}q$" ke saath commute karte hain — yeh Modular Arithmetic ka ek theorem hai. Isliye har step mod $q$ karne se wahi remainder milta hai jaise pehle bada number compute karo aur end mein reduce karo. Division mod ke saath survive nahi karta, isliye hamare hash mein sirf $+,-,\times$ use hota hai.

Rolling update formula ::: $H_{i+1}=((H_i-T[i]\cdot b^{m-1})\cdot b+T[i+m])\mathrm{mod}q$ Double-hash hit ke baad verification kyun rakhein? ::: Exactly correct rehne ke liye; rare/adversarial collision hi woh cheez hai jo "probably equal" aur "equal" ke beech khadi hai.