Boyer-Moore — bad character, good suffix heuristics: Worked examples

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

Yeh hands-on companion note hai parent note ka. Wahan humne do rules banaye the; yahan hum unhe drive karte hain har us situation se jo ek real text mein aa sakti hai. Yeh page self-contained hai: har symbol jo yahan use hota hai, use pehle neeche (re)build kiya gaya hai.

Recall Teen numbers jo hamesha chahiye

$j$ ::: woh pattern index jahan mismatch hua (hum right to left compare karte hain, isliye $j$ $m - 1$ se start hota hai).
$c = T [s + j]$ ::: bad character — woh text character jo mismatch ke neeche baitha hai (yaad rakho $s$ woh alignment offset hai jo upar define kiya gaya hai).
$last (c)$ ::: $P$ ke andar woh rightmost index jahan character $c$ appear karta hai, ya $- 1$ agar $c$ kabhi appear hi nahi karta.

Bad-character shift: $shift_{b c} = max (1, j - last (c))$ . Good-suffix shift: $shift_{g s} = G [j + 1]$ (array $G$ bilkul neeche banaya gaya hai). Total shift: $max (shift_{b c}, shift_{g s})$ .

Do building blocks jo pehle chahiye

Kisi bhi example se pehle hum un do ideas ko define karna zaroori hai jinpar good-suffix rule tika hua hai: ek border, aur good-suffix shift array $G$ . Hum inhe yahan scratch se banate hain taaki is page par kuch bhi bahar se borrowed na ho.

Definition Good-suffix shift array

$G$ $G$ ek table hai jisme har possible mismatch position ke liye ek entry hai. Jab hum pattern index $j$ par mismatch karte hain, suffix $P [j + 1 .. m - 1]$ pehle se text se match ho chuka hota hai — hum $G [j + 1]$ lookup karte hain safe jump paane ke liye. $G$ ko hum do sources se bharte hain, jo good-suffix rule ke do cases se match karte hain:

Case 1 (internal reoccurrence): agar matched suffix $P [j + 1.. m - 1]$ $P$ ke andar kahin pehle bhi appear karta hai, aur us earlier copy se pehle wala character $P [j]$ se alag hai, toh hum us earlier copy ko align karne ke liye shift karte hain. Shift $= (end index of P) - (end index of earlier copy)$ .
Case 2 (border fallback): agar aisa koi full earlier copy nahi milta, toh hum $P$ ka woh sabse lamba border align karte hain jo matched suffix ka bhi suffix ho. Shift $= m - (us border ki length)$ .
Default: agar dono mein se kuch bhi apply nahi hota, shift $= m$ (poora pattern aage slide kar do).
Full match (mismatch index $j = - 1$ ): hum $G [0] = m - (longest proper border of P)$ use karte hain.

Neeche diya hua har example apni zaroorat ka exact $G$ entry seedha inhi rules se compute karta hai, toh tum har number ko haath se reproduce kar sakte ho.

Scenario matrix

Search ke dauran har mismatch ya full match neeche diye gaye algorithmic cases A–H mein se exactly ek mein fit hota hai. (Cases I aur J naye cases nahi hain — yeh woh contexts hain jisme wahi A–H logic exercise hota hai; hum examples ko inse sirf isliye tag karte hain taaki rules ko realistic pressure mein dikha sakein.)

Case	Situation	Shift kya decide karta hai	Galat karo toh kya risk
A	Bad char $P$ mein hai hi nahi ( $last (c) = - 1$ )	poora pattern aage slide: $j + 1$	koi nahi — yeh aasaan bada jump hai
B	Bad char $j$ ke left mein ( $last (c) < j$ )	$j - last (c) \geq 1$	yeh exist karna bhool jana → bahut slow
C	Bad char $j$ ke right mein ( $last (c) > j$ )	formula $\leq 0$ ho jaata hai → clamp to 1	infinite loop / backward shift
D	Mismatch bilkul pehle compare par ( $j = m - 1$ )	abhi tak koi matched suffix nahi, isliye $G [m]$ chhota hai; bad char rules	good suffix par zyada trust karna
E	Good suffix internally reoccur karta hai (Case 1)	us earlier copy ko align karo jiske preceding char alag ho	aisa copy lena jiska same preceding char ho → repeat mismatch
F	Sirf $P$ ka ek border = good suffix ka suffix (Case 2)	us border ko align karo, shift $= m - border$	Case 2 bhool jana → over-shift, match miss
G	Full match mila ( $j$ neeche $0$ se chala jaata hai)	$G [0]$ se shift karo	$1$ se shift karna kaam bekar karta hai; $m$ se shift overlaps skip kar sakta hai
H	Degenerate pattern ( $P = aaa...$ )	worst case $O (nm)$ ; Galil rule fix karta hai	yeh sochna ki BM hamesha fast hai

Neeche use hone wale context tags: I = real-world large-alphabet search (DNA), jahan Case A baar baar fire hota hai → sublinear; J = exam-style "do rules mein se $max$ kaun jeetataa hai?".

Example 1 — Case C phir Case A (context I: real-world DNA)

Step 1 — line up karo aur right-to-left padho (alignment (i)). $P [7] = C$ ; text char hai $T_{1} [7]$ . $T_{1}$ ko 0 se count karte hue: G C T T C T G C → $T_{1} [7] = C$ . Match, $j = 6$ par jao. Yeh step kyun? BM right-to-left compare karta hai; ek match ek matched suffix chheel deta hai.

Step 2 — pehla mismatch pakdo (alignment (i)). $P [6] = G = T_{1} [6]$ ✓; $P [5] = T = T_{1} [5]$ ✓; $P [4] = T$ vs $T_{1} [4] = C$ → mismatch. Toh $j = 4$ , $c = C$ . Yeh step kyun? Pehli disagreement hi decision point hai.

Step 3 — yeh Case C hai (bad char right mein). $last (C)$ in CCTTTTGC = index 7. Kyunki $7 > j = 4$ , naive $4 - 7 = - 3$ illegal hai (backward). Clamp: $shift_{b c} = max (1, 4 - 7) = 1$ . Yeh step kyun? Ek rightmost copy ko jo mismatch ke right mein ho align karna $P$ ko peeche kheench dega.

Step 4 — ek clean Case A (alignment (ii)). Yahan $T_{2} = CCTTATGC$ at $s = 0$ . Right-to-left compare karo: $P [7] = C = T_{2} [7]$ ✓; $P [6] = G = T_{2} [6]$ ✓; $P [5] = T = T_{2} [5]$ ✓; $P [4] = T$ vs $T_{2} [4] = A$ → mismatch at $j = 4$ , $c = A$ . Character A CCTTTTGC mein absent hai, isliye $last (A) = - 1$ aur $shift_{b c} = max (1, 4 - (- 1)) = 5$ — Case A jump, jin characters ko humne kabhi padha hi nahi unhe skip karte hue. Yeh step kyun? Case A aur Case C genuinely alag hain; dono ko apna-apna concrete text dena shift ko poori tarah reproducible rakhta hai.

Verify: Case C → $max (1, 4 - 7) = 1$ . Case A → $max (1, 4 + 1) = 5$ . Dono positive aur legal. ✓

Example 2 — Case B (bad char left mein)

Step 1 — bad character locate karo. $c = C$ . Kyun? Mismatch ke neeche ka text char bad-character rule drive karta hai.

Step 2 — $last (C)$ compute karo. A B C A B mein sirf ek C hai index 2 par. Toh $last (C) = 2$ . Kyun? Hum $P$ ke andar $c$ ki rightmost copy chahte hain taaki use mismatch position ke neeche slide kar sakein.

Step 3 — formula apply karo. $last (C) = 2 < j = 3$ → Case B. $shift_{b c} = max (1, 3 - 2) = 1$ . Kyun? Ek leftward occurrence ek positive, legal shift deta hai — yahan sirf 1, chhota par valid.

Verify: $max (1, 3 - 2) = 1 > 0$ . Index-2 C ko text position $s + 3$ ke neeche align karna $P$ ko exactly $j - last (c) = 1$ right move karta hai. ✓

Example 3 — Case C (bad char right mein, clamp)

Step 1 — $last (A)$ . ABCAB mein, A positions 0 aur 3 par appear karta hai; rightmost 3 hai. Kyun? Standard bad-character lookup.

Step 2 — $j$ se compare karo. $last (A) = 3 > j = 2$ → Case C. Kyun? Rightmost A mismatch ke right mein hai, isliye naive formula $2 - 3 = - 1$ deta hai.

Step 3 — clamp karo. $shift_{b c} = max (1, - 1) = 1$ . Kyun? $- 1$ ka shift $P$ ko left move karta hai, wahi region dobara-dobara padhte raho forever. $max (1, \cdot)$ guard isse rokta hai. Good-suffix rule usually yahan ek bada legal jump deta hai.

Verify: $max (1, 2 - 3) = 1$ . Clamp ke bina $- 1$ milta → non-terminating loop. ✓

Example 4 — Case E (good suffix reoccurs, Case 1)

Figure — Boyer-Moore — bad character, good suffix heuristics

Figure kaise padhein: top row hai ANPANMAN jisme har character apne box mein hai aur neeche uska index. Indices 6–7 par do red-outlined boxes hain jo matched good suffix AN hain. Neeche drawn do red boxes, indices 3–4 par, AN ki earlier internal copy hain; kala arrow us preceding character $P [2] = P$ ki taraf point karta hai. Lamba red arrow pattern ko $6 - 3 = 3$ right slide hote dikhata hai taaki earlier AN already-matched text ke neeche aa jaaye.

Step 1 — good suffix $t$ identify karo. $t = P [6..7] = AN$ (length $m - 1 - j = 8 - 1 - 5 = 2$ ). Kyun? Mismatch ke right mein sab kuch text se match ho chuka hai; hum woh preserve karna chahte hain.

Step 2 — $t$ ke internal reoccurrences dhundho. Jaise figure mein dikhaya gaya hai, AN indices 0–1 aur 3–4 par baitha hai. Hum woh chahte hain jiske preceding character mismatched $P [j] = M$ se alag ho. Kyun? Agar preceding char bhi M hota, toh agla compare identically mismatch karta — koi progress nahi.

Step 3 — indices 3–4 wali copy chunno. Uska preceding char hai $P [2] = P \neq = M$ ✓. AN ko indices 3–4 se indices 6–7 tak laane ke liye, $6 - 3 = 3$ shift karo. Kyun? Hum $P$ ko right slide karte hain taaki earlier valid AN already-matched text ke neeche aa jaaye.

Step 4 — shift-by-1 se sanity check. 1 se shift karne par $P [7] = N$ text ki us position par aa jaata jiske baare mein hum jaante hain ki wahan A hai → guaranteed mismatch. Isliye $shift_{g s} = 3$ beats 1.

Verify: Case 1 shift $=$ (end index 7) $-$ (earlier copy ka end index 4) $= 3$ , isliye $G [j + 1] = G [6] = 3$ ; matched-suffix length $= 2$ . ✓

Example 5 — Case F (Case 2, border = good suffix ka suffix)

Step 1 — good suffix. $t = P [3] = B$ , length $m - 1 - j = 4 - 1 - 2 = 1$ , mismatch at $j = 2$ . Kyun? Matched-suffix length $= m - 1 - j = 1$ .

Step 2 — Case 1 mein kuch usable nahi, toh Case 2 par jao. Kyun? Koi earlier full copy of B nahi hai jiske preceding character ka difference ek immediate repeat mismatch avoid kare; hum ek partial overlap salvage karte hain.

Step 3 — $P$ ka longest border dhundho. ABAB ka aage se reading hai A,B,…; peeche se reading hai B,A,…. Length-2 chunk AB pehle do aur aakhri do characters dono hai → length 2 ka border (border definition yaad karo upar se). Kyun? Border $P$ ke start aur apni tail ke beech ka sabse bada overlap hai, woh eklauta alignment jo bina kisi occurrence ko skip kiye abhi bhi match kar sakta hai.

Step 4 — shift $= m - (border length) = 4 - 2 = 2$ . Kyun? Slide karo taaki length-2 border prefix wahan land kare jahan length-2 border suffix tha.

Verify: ABAB ka longest border 2 hai, isliye Case-2 shift $= m - 2 = 2 > 0$ . Chhota shift sirf impossible alignments re-examine karta hai; bada wala border overlap skip kar deta hai → ek match miss ho sakta hai. ✓

Example 6 — Case D (bilkul pehle compare par mismatch)

Step 1 — matched suffix length. $m - 1 - j = 6 - 1 - 5 = 0$ . Empty suffix. Kyun? Hum kuch bhi match kiye bina mismatch kar gaye, isliye good-suffix lookup hai $G [m] = G [6]$ , empty matched suffix ke liye entry.

Step 2 — $G [6] = G [m]$ cleanly compute karo. Good-suffix rule hum se sirf ek matched suffix preserve karne ko keh sakta hai; jab woh suffix empty ho toh preserve karne ke liye kuch hai hi nahi, isliye rule algorithm ke minimum legal move $1$ se zyada koi constraint nahi lagataa. Concretely $G [m] = 1$ : ek empty good suffix trivially har alignment par overlap karta hai, isliye $P$ ka sabse bada border-of-the-good-suffix jo $P$ ko bhi prefix karta hai uski length $m - 1$ hai (poora pattern minus ek step), jo deta hai $m - (m - 1) = 1$ . Koi contradiction nahi — good-suffix rule yahan simply neutral value $1$ contribute karta hai. Kyun? Ek empty matched suffix mein yeh batane ki zero information hoti hai ki $P$ aage kahan align ho sakta hai, isliye woh $1$ se bada jump legally demand nahi kar sakta.

Step 3 — bad character. $last (K)$ in NEEDLE $= - 1$ → Case D ke andar Case A. $shift_{b c} = max (1, 5 - (- 1)) = 6$ . Kyun? K absent hai, isliye poora pattern use past slide kar do.

Step 4 — max lo. $shift = max (shift_{b c}, G [6]) = max (6, 1) = 6$ . Kyun? Dono rules independently safe lower bounds hain; bada wala jeetta hai. Yahan bad-character rule already maximum possible jump $m = 6$ hit kar leta hai, aur neutral good-suffix value $1$ use beat nahi kar sakta.

Verify: $G [6] = 1$ ; $shift_{b c} = max (1, 5 + 1) = 6 = m$ ; final $max (6, 1) = 6$ . ✓

Example 7 — Case G (full match) + context J (kaun sa rule jeetta hai)

Step 1 — full match ke baad, $G [0]$ use karo. Har character match hone ke baad, $j$ $- 1$ par aa jaata hai; koi bad character lookup karne ke liye hai nahi, isliye shift poori tarah poore pattern ke liye good-suffix rule se aata hai, jo $G [0]$ mein stored hai. Kyun? Bad-character rule trigger karne ke liye koi mismatch nahi; $G [0]$ humein batata hai ki aagla alignment kahan ho sakta hai bina kisi overlapping occurrence ko skip kiye.

Step 2 — ABCAB ka longest border. Aage se reading A,B,C,…; peeche se reading B,A,C,…. Bade se chhote test karo: length 4 ABCA vs BCAB ✗; length 3 ABC vs CAB ✗; length 2 AB vs AB ✓. Toh sabse lamba proper border length 2 ka hai. Kyun? Agla alignment jo match kar sakta hai use $P$ ka sabse bada self-overlap reuse karna hoga — wahi exactly uska longest border hai.

Step 3 — $G [0]$ compute karo. $G [0] = m - (border length) = 5 - 2 = 3$ . Match report karne ke baad hum $s$ ko 3 se advance karte hain. Kyun? 1 ya 2 se shift karna AB… ko wahan rakhega jahan yeh re-match nahi kar sakta; 4 ya 5 se shift karna ek overlapping occurrence ko skip kar sakta hai jo abhi-abhi matched region ke andar shuru hoti hai.

Step 4 — context J twist ( $max$ of the two rules). Usi search mein kisi mismatch ke dauran hum hamesha $max (shift_{b c}, shift_{g s})$ lete hain. Do illustrative pairs:

agar $shift_{b c} = 2$ aur $shift_{g s} = 3$ ho, toh algorithm $max (2, 3) = 3$ use karta hai (good suffix jeetta hai);
agar $shift_{b c} = 5$ aur $shift_{g s} = 3$ ho, toh $max (5, 3) = 5$ use karta hai (bad char jeetta hai). Kyun? Har rule independently ek safe lower bound hai ek legal jump par, isliye bada bhi safe hai — hamesha dono compute karo aur max lo.

Verify: ABCAB ka border 2 hai, $G [0] = 5 - 2 = 3$ . Aur $max (2, 3) = 3$ , $max (5, 3) = 5$ . ✓

Example 8 — Case H (degenerate pattern, worst case)

Step 1 — har alignment compare karo. Har offset $s$ par, right-to-left compare karte hue, $P [2], P [1], P [0]$ saare text A ke barabar hote hain. Hum $m = 3$ comparisons karte hain, full match paate hain, aur (Case G) $G [0]$ se shift karte hain. Kyun? Kuch bhi kabhi mismatch nahi karta, isliye koi bad-character skip kabhi trigger nahi hota.

Step 2 — AAA ke liye $G [0]$ . Aage se reading A,A,…; peeche se reading A,A,…. Sabse lamba proper border: length 2 (AA pehle do aur aakhri do dono characters hai). Toh $G [0] = m - 2 = 3 - 2 = 1$ — hum sirf 1 se shift karte hain har baar. Kyun? AAA khud se har offset par overlap karta hai, isliye post-match ek hi safe move ek single step hai; bada jump overlapping AAA skip kar deta.

Step 3 — kaam count karo. Alignments ki sankhya $= n - m + 1 = 8 - 3 + 1 = 6$ ; har ek $m = 3$ comparisons karta hai aur 1 se shift karta hai. Total $= 6 \times 3 = 18$ comparisons $= O (nm)$ . Kyun? Bad char useless hai (har char A hai) aur good suffix 1 se shift karta hai, isliye BM is input par naive $O (nm)$ bound par degrade ho jaata hai.

Step 4 — fix. Galil Rule already-matched region yaad rakhta hai taaki use kabhi re-compare na kare, guaranteed $O (n)$ yahan bhi restore karta hai. Related always-linear matchers: Knuth-Morris-Pratt (KMP), Z-Algorithm (dono Borders and Prefix Function par built), aur hashing-based Rabin-Karp. Ek saath kai patterns ke liye, Aho-Corasick.

Verify: alignments $= 8 - 3 + 1 = 6$ ; comparisons $= 6 \times 3 = 18$ ; AAA ka border $= 2$ isliye $G [0] = 3 - 2 = 1$ . ✓

Recall

Recall Quick self-test

Alignment offset $s$ kya hai? ::: Woh text position jiske neeche $P [0]$ currently baitha hai; $P [i]$ $T [s + i]$ ke saath line up karta hai. Ek string ka border kya hota hai? ::: Ek substring jo prefix bhi ho aur suffix bhi, poori string se chhota (ek proper border). Kaun se case mein $last (c) = - 1$ hota hai? ::: Case A — bad char absent, shift $= j + 1$ . Kaun sa case clamp to 1 force karta hai? ::: Case C — $last (c) > j$ . Full match ke baad tum kitna shift karte ho? ::: $G [0] = m - (longest border of P)$ . Good suffix ka Case 2 kab fire karta hai? ::: Sirf jab $P$ ka ek border good suffix ke suffix ke barabar ho; shift $= m - border length$ . Do rule shifts ka $max$ kyun lete hain? ::: Har ek independently ek safe lower bound hai, isliye bada bhi safe aur faster hai.