Visual walkthrough — Boyer-Moore — bad character, good suffix heuristics

3.8.5 · D2 · Coding › String Algorithms › Boyer-Moore — bad character, good suffix heuristics

---

Step 1 — Hum kar kya rahe hain? Text, pattern, alignment

KYA HAI. Hum $P$ ko $T$ ke neeche slide karte hain aur check karte hain "kya pattern yahan baithta hai?"

KYUN. Har string-matching algorithm yahi same sliding game hai — Knuth-Morris-Pratt (KMP), Rabin-Karp, sab ke sab. Fark sirf isme hai ki woh har baar kitna slide karte hain. Boyer-Moore ki poori trick hai zyada slide karna.

PICTURE. Green row $T$ hai, blue row $P$ hai jo shift $s$ par rakhi hai (matlab $P[0]$ $T[s]$ ke neeche baitha hai). Choti arrow dikhati hai ki $P[i]$ $T[s+i]$ ke saath line up hoti hai.

---

Step 2 — Right se compare kyun karein?

KYA HAI. Ek insaan ki tarah $P[0]$ pehle check karne ke bajaye, hum aakhri character $P[m-1]$ se shuru karte hain aur backwards chalte hain.

KYUN. Right end ke paas discover hua mismatch prove karta hai ki poori tail pehle se match ho chuki hai. Ek matched tail (ek suffix) ko jaanna hi humein huge distances skip karne deta hai. Agar hum left-to-right compare karte to hum sirf ek matched head ke baare mein jaante, jo jump ke liye bahut kam useful hai.

PICTURE. Red pointer right se shuru hota hai aur left move karta hai. Green cells equal hain ($P[i]=T[s+i]$); pehla red cell mismatch hai.

---

Step 3 — Bad character ka ek sawaal

KYA HAI. Hum pattern ke andar ek $c$ dhundhte hain jo text ke $c$ se line up ho sake.

KYUN. Agar hum ek matching $c$ ko $s+j$ ke neeche align kar sakein, to woh slot ab guaranteed fail nahi hoga. Koi bhi alignment jo pattern ka non-$c$ letter text ke $c$ ke upar rakhti hai woh fail hogi, isliye hum unhe skip kar sakte hain.

PICTURE. Text ka $c$ fixed hai (yellow). $P$ ke andar hum har woh position highlight karte hain jismein bhi $c$ hai; arrows candidate slides dikhate hain.

---

Step 4 — $P$ mein kaunsa $c$? Sabse rightmost wala jo left mein ho

KYA HAI. $P$ ke saare $c$'s mein se, hum woh choose karte hain jo sabse rightmost ho aur jiska index $j$ se kam ho.

KYUN. Aisa sabse rightmost $c$ chunna sabse chota safe slide deta hai — hum kisi aisi alignment ko kabhi nahi laanghte jo match ho sakti thi. (Koi $c$ aur left se choose karna zyada slide karega, shayad ek real match ke upar se kood jayega. Hum sabse bada jump chahte hain jo abhi bhi safe ho, aur rightmost-to-the-left copy exactly woh boundary hai.)

PICTURE. $P$ mein $c$ ke do copies; green arrow $j$ ke left mein sabse rightmost wala chunti hai, use text $c$ ke neeche slide karti hai. Greyed-out arrow ($j$ ke right ki copy) illegal hai — woh pattern ko backwards le jaayega.

---

Step 5 — Picture ko shift number mein badalna

KYA HAI. Hum derive karte hain kitna right slide karein taaki $P[\text{last}(c)]$ $T[s+j]$ ke neeche aa jaaye.

KYUN. Mismatch pattern index $j$ par hai; target copy index $\text{last}(c)$ par hai. Pattern ko $(j-\text{last}(c))$ se right slide karna index $\text{last}(c)$ ko wahan le jaata hai jahan index $j$ tha.

PICTURE. Bracket gap $j-\text{last}(c)$ naap raha hai — exactly utne columns blue pattern right jump karta hai.

---

Step 6 — Teen signs: positive, zero-or-negative, aur clamp

Yeh case-coverage step hai. Raw shift $j-\text{last}(c)$ positive, zero, ya negative ho sakta hai — humein teeno handle karne honge.

Case A — $\text{last}(c)<j$ (copy left mein hai). To $j-\text{last}(c)\ge 1$: ek genuine forward jump. Safe, ho gaya.

Case B — $\text{last}(c)=-1$ (koi copy nahi). To shift $=j+1$: maximum jump, Step 5 mein cover kiya.

Case C — $\text{last}(c)>j$ (sabse rightmost copy mismatch ke right mein hai). To $j-\text{last}(c)<0$ — formula pattern ko backwards ya bilkul nahi slide karna chahta hai. Yeh illegal hai: yeh same columns ko baar baar examine karega, ek infinite loop.

KYUN clamp. Backwards ya zero shift kabhi progress nahi karta. Sabse chota legal forward move $1$ hai, isliye hum raw shift aur $1$ mein se bada lete hain.

PICTURE. Teen mini-panels, ek per sign. Panel C mein backwards arrow crossed out hai aur exactly $1$ ke shift se replace kiya gaya hai.

---

Step 7 — Ek fully worked bad-character jump

---

Step 8 — Doosra, independent jump: good suffix (sketch)

KYA HAI. Matched tail $P[j+1\dots m-1]$ (good suffix $t$) jaani mani hai ki sahi baitha hai. Hum $P$ ko slide karte hain taaki ya to $t$ ki ek aur internal copy, ya $P$ ka ek matching prefix, us pehle se matched text par wapas land kare.

KYUN. Bad-character matched tail ko bilkul ignore karta hai. Good-suffix rule use karta hai, aur weak cases mein (jaise Step 7 ka shift of $1$) woh bahut bada legal jump deta hai. Kisi string ki ek border woh proper substring hai jo prefix bhi hai aur suffix bhi — dekho Borders and Prefix Function; wahi idea hai jo good-suffix table ko computable banata hai.

PICTURE. Top: good suffix $t$ (green) matched. Middle: Case 1 — $t$ ki ek internal copy jiske preceding character $P[j]$ se alag hai text ke neeche slide hoti hai. Bottom: Case 2 — koi full internal copy nahi, isliye $P$ ka ek prefix jo $t$ ke suffix ke barabar hai align hota hai.

---

Ek-picture summary

Final figure poori derivation compress karta hai: right-to-left scan $j$ par bad character $c$ ke saath mismatch dhundh leta hai; bad-character rule sabse rightmost $c$ ko (clamped to $\ge 1$) forward kheenchta hai; good-suffix rule matched tail ko re-align karta hai; actual jump donon ka max hota hai.

Recall Feynman retelling — plain words mein kaho

Chote pattern ko lambe text ke neeche line karo. Right end se checking shuru karo aur left chalte jao. Jis moment do letters disagree karein, us text letter ko dekho jisne use toda — use $c$ kaho. Poochho: "kya mere pattern mein pehle kahin ek $c$ hai jise main slide karke yahan la sakta hoon?" Sabse rightmost aisa $c$ jagah par le aao — yeh $j-\text{last}(c)$ columns hain. Agar koi $c$ hi nahi hai, poore pattern ko uske past jump karo. Agar akela $c$ break ke right mein baitha hai, to woh slide backwards jaayega, isliye sirf ek se nudge karo. Saath hi, woh tail jo tumne pehle se match ki hai woh precious information bhi hai: slide karo taaki us tail ki ek repeat (ya pattern ka matching front) uske upar wapas land kare. Tumhare paas do honest jump numbers hain; bada wala lo. Kyunki right par ek akela failed comparison kai unread letters skip karne ki permission de sakta hai, bade alphabets par tum often $n$ se kaafi kam characters padhte ho — yahi sublinear win hai. Isse compare karo Knuth-Morris-Pratt (KMP) aur Z-Algorithm se, jo text kabhi skip nahi karte lekin linear time guarantee karte hain; Galil Rule Boyer-Moore ke worst case ko bhi $O(n)$ tak patch karta hai.

Recall Quick self-test

Mismatch index $j$ par raw bad-character shift? ::: $j-\text{last}(c)$ $\max (1,\cdot )$ se clamp kyun karein? ::: zero/backward shift (infinite loop) rokne ke liye jab $\text{last}(c)\ge j$ ho Shift jab $c\notin P$ ho? ::: $j+1$ (via $\text{last}(c)=-1$) Final combined Boyer-Moore shift? ::: $\max ({\text{shift}}_{bc},{\text{shift}}_{gs})$