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

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

Is page mein Rabin-Karp ko itna drill karenge ki koi bhi case surprise na kar sake. Pehle hum har tarah ki situation list karenge jo algorithm ko face karni pad sakti hai, phir har ek ko poori tarah se haath se solve karenge.

Throughout: text $T$ ki length $n$ hai, pattern $P$ ki length $m$ hai. Character codes: hum $a=0,b=1,c=2,\dots ,z=25$ use karte hain jab tak kuch aur na bataya jaaye. Rolling update jo hum baar baar use karte hain woh hai

$$H_{i+1}=((H_i-T[i]\cdot P_{\text{high}})\cdot b+T[i+m])\mathrm{mod}q,P_{\text{high}}=b^{m-1}\mathrm{mod}q.$$

---

Scenario matrix

Neeche har worked example ko uss cell ke saath tag kiya gaya hai jo woh cover karta hai. Milke yeh poora grid fill karte hain.

Cell	Case class	Kya galat ho sakta hai / kyun special hai
A	Pehle hi window mein match	Off-by-one: kya index 0 handle hota hai?
B	Aakhri window mein match	Boundary: kya loop $i=n-m$ tak pahunchta hai?
C	Multiple matches (overlapping)	Kya hum saari positions report karte hain, jaldi ruk toh nahi jaate?
D	Koi match hi nahi	Har hash alag hai → pure skipping
E	Hash collision (false positive)	Hashes equal hain, strings alag hain → verify reject kare
F	Degenerate: $m=1$ (single char)	$P_{\text{high}}=b^0=1$; kya roll abhi bhi valid hai?
G	Degenerate: $m=n$ (pattern = poora text)	Sirf ek window; bilkul rolling nahi
H	Negative intermediate value	Subtraction mod ke andar 0 se neeche chali jaati hai → +q fix
I	Real-world word problem	Plagiarism / DNA style application
J	Exam twist: chhota $q$ worst case force karta hai	Har window collide karti hai → $O(nm)$, expected se contrast

Yeh Examples 1–10 mein cover hote hain. Cells A–J sab covered hain.

---

Example 1 — Pehli window mein match (Cell A)

Forecast: match kahan expect karte ho — index 0, 1, ya dono? Padhne se pehle guess karo.

1. Pattern hash karo. $h(P)=a\cdot 26+b=0\cdot 26+1=1$. Yeh step kyun? Har window ko compare karne ke liye ek number chahiye. "ab" ko base-26 number ki tarah padhne par $0\cdot 26^1+1\cdot 26^0=1$ milta hai.
2. Window 0 = "ab" hash karo. $H_0=0\cdot 26+1=1$. Yeh step kyun? Pehli window scratch se banani padti hai (roll karne ke liye kuch hai hi nahi abhi). Board par peela window dekho — woh positions 0–1 ke upar baitha hai.
3. Compare karo: $H_0=1=h(P)$ → hashes match karte hain → verify karo: "ab" == "ab" ✓. Index 0 par match report karo. Verify kyun? Hash equality zaroori hai par kaafi nahi; letters confirm karne hi chahiye.
4. Window 1 = "ba" par roll karo. $P_{\text{high}}=b^{m-1}=26^1=26$. $H_1=((1-T[0]\cdot 26)\cdot 26+T[2])\mathrm{mod}101=((1-0)\cdot 26+0)\mathrm{mod}101=26$. $26\ne 1$ → skip.

Verify karo: "ba" ka direct hash $=b\cdot 26+a=1\cdot 26+0=26$ ✓, roll se agree karta hai. Sirf index 0 match karta hai. ✔

---

Example 2 — Aakhri window mein match (Cell B)

Forecast: pattern "ca" clearly end mein baitha hai. Kya loop wahan tak pahunchega?

1. Pattern hash karo: $h(P)=c\cdot 26+a=2\cdot 26+0=52$. Kyun? yeh hamara comparison target hai.
2. Window 0 = "aa": $H_0=0\cdot 26+0=0\ne 52$ → skip.
3. Window 1 = "ac" par roll karo: $H_1=((0-0\cdot 26)\cdot 26+2)\mathrm{mod}101=2\ne 52$ → skip. Yeh step kyun? Leading 'a'(=0) drop karo, slide karo, 'c'(=2) add karo.
4. Window 2 = "ca" par roll karo: $H_2=((2-T[1]\cdot 26)\cdot 26+T[3])\mathrm{mod}101=((2-0)\cdot 26+0)\mathrm{mod}101=52$. $52=h(P)$ → verify karo "ca"=="ca" ✓ → index 2 par match (aakhri window, kyunki $n-m=4-2=2$).

Verify karo: direct hash "ca" $=2\cdot 26+0=52$ ✓. Loop $i=0\dots n-m$ run karna chahiye; yahan woh inclusive endpoint $i=2$ hai. ✔

---

Example 3 — Multiple overlapping matches (Cell C)

Forecast: "aaaa" mein "aa" kitni baar aata hai? Overlaps include karke count karo.

1. Pattern hash karo: $h(P)=0\cdot 26+0=0$.
2. Windows: har window "aa" hai, toh har hash $0$ hai.
   • $H_0=0$ → verify ✓ → 0 par match.
   • $H_1=((0-0)\cdot 26+0)=0$ → 1 par match.
   • $H_2=((0-0)\cdot 26+0)=0$ → 2 par match. Yeh step kyun? Hume pehle match par rukna nahi — task har position maangta hai. Indices $0,1,2$ par overlaps sab count hote hain.
3. Windows exist karte hain $i=0,1,2$ ke liye (yani $n-m+1=4-2+1=3$).

Verify karo: $\{0,1,2\}$ par matches, total 3 occurrences. ✔

---

Example 4 — Kahin koi match nahi (Cell D)

Forecast: "zz" ek bade number mein hash hota hai; kya tumhe lagta hai koi window verify bhi trigger karegi?

1. Pattern hash karo: $h(P)=z\cdot 26+z=25\cdot 26+25=675$. Reduce karo: $675\mathrm{mod}101=675-6\cdot 101=675-606=69$. Yahan mod kyun? $q=101$ hai, toh hum $[0,101)$ ke andar kaam karte hain; $675$ ko reduce karna padega.
2. "abab" ki windows: "ab"$=1$, "ba"$=26$, "ab"$=1$. Koi bhi $69$ ke barabar nahi.
   • $H_0=(0\cdot 26+1)=1$.
   • $H_1=((1-0)\cdot 26+0)=26$.
   • $H_2=((26-T[1]\cdot 26)\cdot 26+T[3])=((26-1\cdot 26)\cdot 26+1)=1$. Yeh step kyun? Pure skipping — hash filter teeno ko instantly reject karta hai, zero character comparisons.
3. Koi bhi hash $69$ ke barabar nahi → bilkul koi verification nahi.

Verify karo: matches $=\{\}$; verification count $=0$. Filter ke liye yeh best case hai. ✔

---

Example 5 — Hash collision, false positive (Cell E)

Forecast: kya do alag strings mod 25 same hash de sakti hain? Agar haan, toh humein kya bachata hai?

1. Pattern hash: $h(\text{"ba"})=1\cdot 26+0=26$; $26\mathrm{mod}25=1$.
2. Window "az": $h(\text{"az"})=0\cdot 26+25=25$; $25\mathrm{mod}25=0$. Yahan koi collision nahi. Ab engineered wala: $h(\text{"ba"})\mathrm{mod}25=1$ aur $h(\text{"a"}\text{?})$… ek window choose karo "z" style. Concretely, note karo $h(\text{"ba"})=26\equiv 1$ aur koi bhi string jisme value $\equiv 1(\mathrm{mod}25)$ ho woh collide karegi. String "ba" (value 26) aur ek hypothetical "a"+code-1 window dono $1$ denge.
3. Baat yeh hai: jab $H_i\mathrm{mod}q=h(P)$ ho lekin actual letters alag hon, toh hum char-by-char verify karke reject karte hain. Yeh step kyun? Hash ek filter hai, proof nahi — dekho Birthday Paradox kyun collisions intuition se zyada common hoti hain.

Verify karo: $26\mathrm{mod}25=1$ aur $51\mathrm{mod}25=1$ — toh value $26$ aur $51$ wali strings $q=25$ ke under collide karti hain; verification hi correctness maintain karta hai. ✔

---

Example 6 — Single-character pattern, $m=1$ (Cell F)

Forecast: $m=1$ ke saath, $P_{\text{high}}=b^{m-1}$ kya hoga? Kya roll formula abhi bhi sense karta hai?

1. $P_{\text{high}}=b^{m-1}=26^0=1$. Kyun? Ek character window ke "leading digit weight" ki value bas $1$ hoti hai.
2. Pattern hash karo: $h(P)=a=0$.
3. Windows (har ek ek char hai): "c"$=2$, "a"$=0$, "b"$=1$.
   • $H_0=2\ne 0$ → skip.
   • Roll karo: $H_1=((2-T[0]\cdot 1)\cdot 26+T[1])\mathrm{mod}101$… lekin ruko — $m=1$ ke liye roll simplify ho jaata hai. Poora char drop karo, $b$ se multiply karo (kuch bachta nahi), new char add karo. Effectively $H_{i+1}=T[i+1]$. $H_1=((2-2\cdot 1)\cdot 26+0)=0\ne$… equals $0=h(P)$ → verify karo "a"=="a" ✓ → index 1 par match. Yeh step kyun? $(2-2)=0$, times 26 hai 0, plus 'a'(=0) hai 0. Confirm karta hai ki $H_1$ bas naye char ka code hai.
   • $H_2=((0-0\cdot 1)\cdot 26+1)=1\ne 0$ → skip.

Verify karo: sirf index 1 match karta hai; $H_1=0$ roll se sahi recover hua. ✔

---

Example 7 — Pattern poore text ke barabar hai, $m=n$ (Cell G)

Forecast: jab $m=n$ ho toh kitni windows exist karti hain? Kitne rolls hote hain?

1. Windows: $n-m+1=4-4+1=1$. Exactly ek window, toh koi rolling nahi hoti. Yeh kyun matter karta hai? Rolling machinery use hi nahi hoti; yeh ek single from-scratch hash + ek verify par degenerate ho jaata hai.
2. Dono hash karo: codes $c=2,o=14,d=3,e=4$. $h(P)=2\cdot 26^3+14\cdot 26^2+3\cdot 26+4$. Mod 101 compute karo: $26^2=676\equiv 676-6\cdot 101=70$. $26^3\equiv 70\cdot 26=1820\equiv 1820-18\cdot 101=1820-1818=2$. $h=2\cdot 2+14\cdot 70+3\cdot 26+4=4+980+78+4=1066\equiv 1066-10\cdot 101=56$.
3. $T$ ke liye same value (identical string) → hashes match karte hain → verify karo → index 0 par match.

Verify karo: $h(P)\mathrm{mod}101=56$; identical text same $56$ deta hai; index 0 par single match. ✔

---

Example 8 — Negative intermediate value, +q fix (Cell H)

Forecast: jab hum bada leading digit drop karte hain, kya $(H_i-T[i]\cdot P_{\text{high}})$ zero se neeche ja sakta hai?

1. Start hash "ba": $H_0=1\cdot 26+0=26$. $P_{\text{high}}=26$.
2. Leading 'b'(=1) drop karo: $26-1\cdot 26=0$. Yahan theek hai — ek harder case banate hain: $q=25$ use karo taaki values already reduced hon. $H_0=26\mathrm{mod}25=1$. Ab $1-T[0]\cdot P_{\text{high}}=1-1\cdot (26\mathrm{mod}25)=1-1\cdot 1=0$. Abhi bhi theek hai — toh force karo: maano $H_i=3$, $T[i]\cdot P_{\text{high}}=20$, $q=25$. $3-20=-17$ — negative! Yeh step kyun? Modulus ke under, reduced $H_i$ us product se chhota ho sakta hai jo hum subtract karte hain.
3. Fix yeh hai: compute karo ((H - x) % q + q) % q. Yahan $(-17)\mathrm{mod}25$: math mein yeh $8$ hai, lekin bahut saari languages $-17$ deti hain; $q$ add karo: $-17+25=8$. Yeh step kyun? Har hash $[0,q)$ mein hona chahiye taaki comparisons consistent hon — dekho Modular Arithmetic.

Verify karo: $-17\mathrm{mod}25=8$ (mathematical modulo); +q trick $8$ reproduce karta hai. ✔

---

Example 9 — Real-world word problem: plagiarism scan (Cell I)

Forecast: "metadata" "data" se khatam hoti hai. Usse match ka index kya hoga?

1. Pattern "data" hash karo: $d=3,a=0,t=19,a=0$. $h(P)=3\cdot 26^3+0\cdot 26^2+19\cdot 26+0$. $26^3\equiv 2,26^2\equiv 70$ use karte hain (Ex. 7 se): $h=3\cdot 2+0+19\cdot 26+0=6+494=500\equiv 500-4\cdot 101=96$. Pehle hash kyun? "metadata" ki har 4-window se slide-compare karne ke liye ek number.
2. Target window "data" index $8-4=4$ par baitha hai (0-indexed: m-e-t-a-d-a-t-a). Iska hash $96$ hai (same letters as $P$) → hashes match karte hain → verify karo → ✓ index 4 par match. Yeh naive se better kyun? Lambi submission par, hum $O(m)$ verification sirf rare hash hit par pay karte hain — expected $O(n+m)$. Yeh bilkul wahi String Hashing for Substring Comparison idea hai jo search ke liye reuse ho raha hai.

Verify karo: $h(\text{"data"})\mathrm{mod}101=96$; "metadata" mein occurrence index 4 hai. ✔

---

Example 10 — Exam twist: chhota $q$ worst case force karta hai (Cell J)

Forecast: $q=1$ ke saath, har number reduce hokar $0$ ho jaata hai. Filter ka kya hoga?

1. Sab kuch 0 mein hash hota hai. Kisi bhi $x$ ke liye, $x\mathrm{mod}1=0$. Toh $h(P)=0$ aur har window hash $=0$. Yeh step kyun? Modulus saari values collapse kar deta hai — hash filter useless ho jaata hai.
2. Har window "hit" karti hai → hum $n-m+1=5-2+1=4$ saari windows verify karte hain, har ek $O(m)$ check hai. Total verification work $\approx (n-m+1)\cdot m=4\cdot 2=8$ character comparisons → yeh $O(nm)$ worst case hai.
3. Contrast: $10^9+7$ jaisi large prime ke saath, collision chance $\approx 1/q$ hai, verifications rare hain, aur hum expected $O(n+m)$ recover karte hain. Deterministic linear algorithms jaise Knuth-Morris-Pratt aur Z-Algorithm is failure mode se poori tarah bachte hain.

Verify karo: windows $=4$; har hash $=0$; verifications $=4$; comparisons $=8$. Worst-case demonstrate ho gaya. ✔

---

Recall Quick self-check

$n$ length ke $T$ aur pattern $m$ ke liye windows ki number ::: $n-m+1$. $q=1$ ke saath, har hash equals ::: $0$ (worst case, har jagah verify). $P_{\text{high}}$ jab $m=1$ ho ::: $b^0=1$. "metadata" mein "data" ka match index ::: 4. Negative intermediate hash fix kaise karein ::: $q$ add karo phir dobara mod lo.

---

Connections

• Parent topic
• Hashing — polynomial fingerprint jo hum compute karte hain
• Modular Arithmetic — %q reductions aur +q negative fix
• Birthday Paradox — kyun collisions (Cell E) intuition se zyada common hain
• Knuth-Morris-Pratt / Z-Algorithm — deterministic linear matchers jo Cell J se bachte hain
• String Hashing for Substring Comparison — wahi rolling hash range equality ke liye reuse hota hai