Boyer-Moore — bad character, good suffix heuristics: Exercises

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

Reminders jo tum constantly use karoge (sab parent se hain):

Puri note mein indices 0-based hain: $P [0]$ pehla character hai, $P [m - 1]$ aakhri.

Neeche di gayi picture har problem ke liye tumhara mental model hai. Isko baar baar dekhte rehna.

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

Figure s01 — Boyer-Moore alignment. Upar wali pale-blue row text $T$ hai; neeche wali row pattern $P$ hai jo ek alignment par rakhi gayi hai. Lavender arrow scan direction dikhata hai: hum $P$ ke right end se shuru karke left ki taraf chalte hain. Mint cells (P ka right portion) matched good suffix hain — woh text ke upar wale characters se already match kar chuke hain. Single coral cell first mismatch hai; uske seedha upar baitha text character bad character $c$ hai. Bad-character rule us coral column par react karta hai; good-suffix rule mint block par react karta hai. Is page ke har exercise mein yahi picture hai bas alag letters ke saath.

Definition Good-suffix array

$G$ — ek baar banao, har jagah use karo Kyunki $G [j + 1]$ aur $G [0]$ is page ke almost har formula mein aate hain, yahan puri array $G [0 \dots m]$ construct karna bataya gaya hai taaki tumhe bar bar parent note pe flip back na karna pade.

$G$ ki length $m + 1$ hai. $G [j + 1]$ woh shift hai jo use hoti hai jab mismatch pattern index $j$ par ho (toh matched suffix ki length $m - 1 - j$ hai). $G [0]$ woh shift hai jo full match ke baad use hoti hai.
Full match / whole-pattern shift ka rule: $G [0] = m - (length of the longest proper border of P)$ . Ek border (L1.3 mein defined) woh string hoti hai jo ek saath proper prefix bhi ho aur proper suffix bhi. Yeh self-overlap ko respect karta hai taaki koi overlapping occurrence miss na ho.
Case 1 (good suffix $P$ ke andar dobara aata hai): agar matched suffix $t = P [j + 1.. m - 1]$ pehle $P$ ke andar kisi aur jagah aata hai alag preceding character ke saath, toh shift karo taaki woh inner copy text ke neeche align ho jaaye — shift $=$ (right end of the matched suffix) $-$ (right end of that inner copy).
Case 2 (sirf $t$ ka ek suffix $P$ ke prefix ke roop mein bachta hai): agar koi full inner copy nahi milti, toh $P$ ka longest prefix jo $t$ ke suffix ke barabar ho use align karo; shift hai $m$ minus us prefix ki length.

Formula

$G$ ke saare values fill karne ka ek concrete step-by-step tarika Ek clean two-pass construction (standard textbook wala) $G [k]$ ko har $k = 0 \dots m$ ke liye $suff []$ array (L3.1 mein defined) se compute karta hai. Yahan $k = j + 1$ matched suffix ke start index ki length hai, aur $G [k]$ shift hai jab matched suffix $P [k .. m - 1]$ ho.

Initialise karo $G [k] = m$ sab $k$ ke liye (safe default — koi match skip nahi karta).
Pass A (Case 2, prefix = suffix). $i$ ko $m - 1$ se $0$ tak walk karo. Ek pointer $lastPrefix$ rakho = ab tak dekha gaya sabse chota start index jiska suffix poore pattern ka prefix hai (yaani $suff [i] = i + 1$ ). Har $k$ ke liye $0$ se $m - 1$ tak jo abhi kisi strong rule se set nahi hua, set karo $G [k] = m - lastPrefix$ . Yeh un positions ko fill karta hai jahan good suffix ka sirf ek suffix $P$ ke prefix ke roop mein bachta hai.
Pass B (Case 1, internal reoccurrence). $i$ ko $0$ se $m - 2$ tak ke liye, $k = m - 1 - suff [i]$ lo; set karo $G [k] = (m - 1) - i$ . Kyunki hum $i$ increasing sweep karte hain, baad ke (bade- $i$ , yaani rightmost) copies pehle wale ko sabse chhoti valid shift se overwrite karte hain — tightest legal jump.
Full match: $G [0]$ automatically Pass A se $m - (longest border)$ ban jaata hai. Is procedure ka ek fully worked run L4.4 mein diya gaya hai.

Level 1 — Recognition

L1.1 $P = NEEDLE$ ( $m = 6$ ) ke liye, har us letter ke liye $last (c)$ likho jo aata hai, aur $last (X)$ batao.

Recall Solution

Pattern ko index karo: $P [0] = N, P [1] = E, P [2] = E, P [3] = D, P [4] = L, P [5] = E$ . $last (c)$ woh rightmost index hai jahan $c$ appear karta hai.

$last (N) = 0$ (sirf index 0 par).
$last (E) = 5$ — E 1, 2, 5 par aata hai; rightmost hai 5.
$last (D) = 3$ .
$last (L) = 4$ .
$last (X) = - 1$ — X aata hi nahi, isliye hum "not present" sentinel $- 1$ return karte hain.

L1.2 Boyer-Moore mein, pattern ka kaun sa end hum pehle compare karte hain, aur kyun?

Recall Solution

Hum pehle rightmost character $P [m - 1]$ ko text se compare karte hain, phir left ki taraf move karte hain. Reason: right ke paas mismatch humein batata hai ki ek poora matched suffix already line up ho chuka tha. Wahi matched suffix exactly hai jo good-suffix rule exploit karta hai, aur mismatching text character woh hai jo bad-character rule exploit karta hai. Agar hum left-to-right compare karte (naive matching ki tarah) toh hum koi suffix nahi seekh paate, aur bade skips impossible ho jaate.

L1.3 Ek string ka "border" kya hota hai, ek sentence mein?

Recall Solution

Ek border ek proper substring hai (poori string nahi) jo ek saath prefix bhi ho aur suffix bhi. Example: ANANA mein string ANA ek border hai (yeh pehle 3 chars bhi hai aur aakhri 3 chars bhi). Yeh Borders and Prefix Function se connect hota hai.

Level 2 — Application

L2.1 $P = ABCAB$ ( $m = 5$ ). Mismatch $j = 2$ par hota hai (toh $P [2] = C$ ) aur wahan text character $c = B$ hai. $shift_{b c}$ compute karo.

Recall Solution

ABCAB mein $last (B)$ : B indices 1 aur 4 par aata hai, isliye $last (B) = 4$ . $shift_{b c} = max (1, j - last (B)) = max (1, 2 - 4) = max (1, - 2) = 1$ . Raw formula ne $- 2$ diya (matlab backward shift hota!), isliye $max (1, \cdot)$ clamp humein bachata hai. Yahan bad-character rule weak hai; real run mein good-suffix rule actual jump provide karega.

L2.2 Wahi $P = ABCAB$ , mismatch $j = 4$ par (last char compare karte waqt) text char $c = Z$ ke saath. $shift_{b c}$ compute karo.

Recall Solution

$last (Z) = - 1$ (Z absent hai). $shift_{b c} = max (1, 4 - (- 1)) = max (1, 5) = 5$ . Kyunki Z $P$ mein kahin nahi hai, hum poore pattern ko us text position ke aage slide karte hain — poori pattern length ka ek jump. Yahi BM ka sublinear magic hai.

L2.3 $P = TATAT$ ( $m = 5$ ). Mismatch $j = 3$ par text char $c = A$ ke saath. $shift_{b c}$ compute karo.

Recall Solution

Index: $P [0] = T, P [1] = A, P [2] = T, P [3] = A, P [4] = T$ . $last (A) = 3$ . Lekin mismatch khud $j = 3$ par hai — bad char bilkul usi index se align ho raha hai jahan mismatch hua. $shift_{b c} = max (1, 3 - 3) = max (1, 0) = 1$ . Clamp phir fire karta hai: $j - last (c) = 0$ matlab "move hi mat karo," jo illegal hai. Hum $1$ lete hain.

Level 3 — Analysis

L3.1 $P = GCAGAGAG$ ( $m = 8$ ) ke liye $suff []$ array compute karo, jahan $suff [i]$ woh length hai — $P$ ke index $i$ par khatam hone wale longest suffix ki — jo poore $P$ ka bhi suffix ho.

Recall Solution

Index: $P = G C A G A G A G$ at $0 \dots 7$ . Whole-pattern suffix right to left padhne par G A G A G A C G aata hai.

$suff [7] = 8$ by convention (poori string khud apna suffix hai).
$suff [6]$ : index 6 par khatam hone wala suffix ...A hai; whole-P G se khatam hota hai. A≠G → $0$ .
$suff [5]$ : index 5 par G hai; compare karo G(P[5]) vs G(P[7]) match; A(P[4]) vs A(P[6]) match; G(P[3]) vs G(P[5]) match; A(P[2]) vs A(P[4]) match; P[1]=C vs P[3]=G stop. Indices 5,4,3,2 par walk → $suff [5] = 4$ .
$suff [4]$ : index 4 par A vs P[7] G → $0$ .
$suff [3]$ : G vs G match; P[2]A vs P[6]A match; P[1]C vs P[5]G stop → $2$ .
$suff [2]$ : A vs G → $0$ .
$suff [1]$ : C vs G → $0$ .
$suff [0]$ : G vs G match, left mein aur chars nahi → $1$ . Result: $suff = [1, 0, 0, 2, 0, 4, 0, 8]$ .

L3.2 $P = ANPANMAN$ ( $m = 8$ ). Good suffix AN (length 2) match hua, mismatch index $j = 5$ par (char $P [5] = M$ ). AN ke do aur copies hain, indices $0 - 1$ aur $3 - 4$ par. Explain karo kyun hum ek copy ko Case-1 candidate ke roop mein reject karte hain, aur hum actually kaun si copy align karte hain.

Recall Solution

Index: $P = A N P A N M A N$ at $0 \dots 7$ . Good suffix hai $P [6..7] = AN$ ; mismatch $j = 5$ par, $P [5] = M$ . Case 1 require karta hai ki good suffix ki kisi internal copy ke just pehle wala character mismatch char $P [j] = M$ se alag ho — warna us copy par slide karne se same relative position par same M aa jaayega aur identical mismatch repeat hoga (zero progress).

$0 - 1$ wali copy ko Case-1 candidate ke roop mein reject karo: iske koi preceding character nahi (yeh $P$ ki bilkul shuruat mein hai). Case 1 ko ek genuinely internal copy chahiye jiske aage ek real preceding char ho test karne ke liye, isliye yeh leading copy Case-1 hit nahi hai — yeh sirf Case-2 / prefix fallback ke through contribute karta hai.
$3 - 4$ wali copy ko accept karo: iska preceding char $P [2] = P$ hai, aur $P \neq = M$ ✓. Yeh ek valid Case-1 copy hai. Toh hum $3 - 4$ wali copy ko text ke AN ke neeche align karte hain. Shift $6 - 7$ wali AN ko wahan move karta hai jahan $3 - 4$ wali AN hai: $shift = 7 - 4 = 3$ . (Agar dono inner copies M se preceded hoti, toh hum Case 2 par jaate aur $P$ ka prefix use karte.)

L3.3 $max (shift_{b c}, shift_{g s})$ lena hamesha safe kyun hai (koi real occurrence skip nahi hota)?

Recall Solution

Har rule independently ek guaranteed lower-bound jump ke roop mein derive kiya gaya hai: "skipped region mein koi valid match start nahi ho sakta." Bad-character rule yeh mismatching text char se prove karta hai; good-suffix rule yeh matched suffix se prove karta hai. Agar jump $a$ safe hai aur jump $b$ safe hai, toh $max (a, b)$ se strictly neeche ka har alignment kam se kam ek proof se rule out hota hai — isliye $max (a, b)$ bhi safe hai. Bada lena matlab hum sirf us proof par trust karte hain jo zyada door tak pahunchta hai.

Level 4 — Synthesis

L4.1 $P = CCTTTTGC$ ( $m = 8$ ). Sab letters ke liye $last (c)$ compute karo, phir $shift_{b c}$ compute karo jab hum kisi $s$ par align karein, right-to-left compare karein, aur pehla mismatch $j = 7$ par text char $c = A$ ke saath ho.

Recall Solution

Index: $P = C C T T T T G C$ at $0 \dots 7$ . $last (C) = 7, last (T) = 5, last (G) = 6, last (A) = - 1$ . Mismatch $j = 7$ , $c = A$ , $P$ mein absent hai: $shift_{b c} = max (1, 7 - (- 1)) = 8$ . Hum poori pattern width jump karte hain, sirf ek text character padhke. Yahi is alignment par BM ka sublinear behaviour hai.

L4.2 Wahi $P = CCTTTTGC$ . Ab maano kisi alignment par $P [7] = C$ match hua lekin $P [6] = G$ mismatch hua, yaani $j = 6$ , text char $c = C$ ke saath. Dono heuristics ke shifts aur final BM shift compute karo. (Good suffix ke liye, matched suffix sirf C hai; $P$ mein pehle wale Cs indices 0,1,7 par hain.)

Recall Solution

Bad character: $c = C$ , $last (C) = 7$ . $shift_{b c} = max (1, 6 - 7) = max (1, - 1) = 1$ . Good suffix: matched suffix hai $t = C$ (length 1), yaani $j = 6$ toh hum $G [7]$ chahte hain. Humein $P$ mein C ki ek aisi pehle wali copy chahiye jiska preceding char mismatch char $P [6] = G$ se alag ho, taaki text ke trailing C ke neeche align kiya ja sake.

Index 1 par C: preceding char $P [0] = C \neq = G$ ✓. $P [7]$ ki C ko us text position par le jaao jo currently $P [1]$ ke target par hai; shift jo $P [1]$ ki C ko us slot par laata hai jahan $P [7]$ ki C hai woh hai $7 - 1 = 6$ .
(C at index 0 ka koi preceding char nahi; index 1 sabse paas wali valid inner copy hai, jo sabse chhota safe good-suffix jump = $6$ deti hai.) $shift_{g s} = G [7] = 6$ . Final: $max (shift_{b c}, shift_{g s}) = max (1, 6) = 6$ . Yahi exactly woh scenario hai jiske baare mein parent note warn karta hai: bad char akele feeble $1$ deta hai; good suffix usse $6$ se rescue karta hai.

L4.3 BM ka trace karo ( $max$ of both heuristics use karte hue) $T = AABAACAADAABAABA$ (text length $n = 16$ ), $P = AABA$ ( $m = 4$ ) par. Har try kiya gaya alignment $s$ aur har reported match list karo. Mismatches par good-suffix rule kya contribute karta hai woh bhi dikhao.

Recall Solution

$P = A A B A$ , indices $0..3$ . $last (A) = 3, last (B) = 2$ , baaki $- 1$ . Yaad rakho $n = 16$ (text length), toh last valid alignment $s = n - m = 12$ par hai. Good-suffix array facts jo chahiye. AABA ka longest proper border A hai (prefix A = suffix A), isliye full-match shift hai $G [0] = m - 1 = 3$ . Neeche ke mismatches mein mismatch hamesha $j = 2$ par hai (chars B vs non-B), isliye matched suffix hai $t = P [3] = A$ (length 1) aur humein $G [3]$ chahiye. $P$ mein pehle wali A kahin milti hai jiska preceding char $P [2] = B$ se alag ho? Index 0 par A ke aage kuch nahi (leading hai), index 3 par A wahi matched wali hai; Case 1 ke liye nearest usable earlier A index 0 via prefix/Case-2 route hai. Calculate karne par AABA ke liye $G [3] = 2$ aata hai. Toh in mismatches par $shift_{g s} = 2$ . Step through karo, hamesha $s \leq n - m = 12$ rakhte hue:

$s = 0$ : $T [0..3] = AABA$ vs AABA compare karo → full match. Report $s = 0$ . Shift $= G [0] = 3 \Rightarrow s = 3$ .
$s = 3$ : $T [3..6] = AACA$ . $P [3] = A$ vs $T [6] = A$ ✓; $P [2] = B$ vs $T [5] = C$ ✗ at $j = 2$ , $c = C$ absent. $shift_{b c} = max (1, 2 - (- 1)) = 3$ ; $shift_{g s} = G [3] = 2$ . Final $= max (3, 2) = 3 \Rightarrow s = 6$ . (Yahan bad char jeetta hai, lekin good suffix ne independently 2 ka jump justify kiya.)
$s = 6$ : $T [6..9] = AADA$ . $P [3]$ ✓; $P [2] = B$ vs $T [8] = D$ ✗ at $j = 2$ , $c = D$ absent. $shift_{b c} = 3$ , $shift_{g s} = 2$ , final $= 3 \Rightarrow s = 9$ .
$s = 9$ : $T [9..12] = AABA$ → full match. Report $s = 9$ . Shift $= G [0] = 3 \Rightarrow s = 12$ .
$s = 12$ : $T [12..15] = AABA$ → full match. Report $s = 12$ . Shift $= 3 \Rightarrow s = 15 > n - m = 12$ . Ruko. Matches $s = 0, 9, 12$ par. Alignments try kiye: ${0, 3, 6, 9, 12}$ — paanch, naive ke $13$ ke muqable mein.

L4.4 $P = GCAGAGAG$ ( $m = 8$ ) ke liye two-pass procedure aur L3.1 ki $suff$ array use karke poora good-suffix array $G [0 \dots m]$ banao. Har pass dikhao.

Recall Solution

L3.1 se: $suff = [1, 0, 0, 2, 0, 4, 0, 8]$ , $m = 8$ . Init: $G = [8, 8, 8, 8, 8, 8, 8, 8, 8]$ (length $m + 1 = 9$ ). Pass A (Case 2, prefix = suffix). Hum woh indices $i$ dhundhte hain jahan $suff [i] = i + 1$ ho (yaani poore pattern ka prefix $i$ par khatam hota hai). Check karo: $suff [0] = 1 = 0 + 1$ ✓ (prefix G). Koi aur $i$ satisfy nahi karta ( $suff [3] = 2 \neq = 4$ , $suff [5] = 4 \neq = 6$ , etc.). Toh sirf ek surviving prefix hai length $1$ ka, start index $lastPrefix$ — sabse chota start hai $m - suff [0] = 8 - 1 = 7$ . Har $k$ ke liye jo abhi kisi strong rule se set nahi hua, fill karo $G [k] = m - lastPrefix = 8 - 7 = 1$ . Concretely yeh un high- $k$ positions pe Case-2 default $G [k] = 1$ set karta hai jahan prefix reach karta hai; $G [0] = m - border = 8 - 1 = 7$ . Pass B (Case 1, internal reoccurrence). $i = 0 \dots m - 2$ ke liye, $k = m - 1 - suff [i]$ set karo aur $G [k] = (m - 1) - i$ , $i$ increasing sweep karte hue taaki rightmost copies tightest shift dein:

$i = 0, suff = 1$ : $k = 7 - 1 = 6$ , $G [6] = 7 - 0 = 7$ .
$i = 3, suff = 2$ : $k = 7 - 2 = 5$ , $G [5] = 7 - 3 = 4$ .
$i = 5, suff = 4$ : $k = 7 - 4 = 3$ , $G [3] = 7 - 5 = 2$ .
( $suff = 0$ wale indices $k = 7$ dete hain, jo $m$ ki taraf harmlessly overwrite hote hain.) Result (ek standard convention): $G = [7, 8, 8, 2, 8, 4, 7, 8, \dots]$ with Case-2 fills of $1$ jo untouched high positions par apply hote hain. Jo do shifts tum sabse zyada use karte ho woh hain $G [0] = 7$ (full-match jump) aur Case-1 entries $G [3] = 2, G [5] = 4, G [6] = 7$ . Key competency: ab tum $suff$ se koi bhi $G [k]$ derive kar sakte ho, guess karne ki zaroorat nahi.

Level 5 — Mastery

L5.1 Woh classic worst case construct karo jahan basic Boyer-Moore $O (nm)$ tak degrade ho jaata hai, aur explain karo kyun dono heuristics help nahi karte. Phir batao isko fix kya karta hai.

Recall Solution

Lo $P = AAAA$ ( $m = 4$ ) aur $T = AAAA...A$ ( $n$ copies of A). Har alignment par, right-to-left scan $j = 0$ tak sab match karta hai (koi mismatch andar nahi), toh hum $m$ comparisons per alignment karte hain. Approximately $n - m + 1$ alignments hain. Total $\approx (n - m + 1) \cdot m = O (nm)$ . Kyun heuristics nahi bachate: good-suffix full-match shift hai $G [0] = m - border = 4 - 3 = 1$ (AAAA ka longest proper border AAA hai, length 3). Bad-character bhi chhote shifts deta hai kyunki har char A hai. Toh hum ek ek karke aage creep karte rehte hain aur matched characters ko baar baar re-read karte hain. Fix: Galil Rule yaad rakhta hai ki previous match kitna aage pahuncha tha aur us region ko re-compare karna skip karta hai, guaranteed $O (n)$ restore karta hai.

L5.2 Tumhare paas ek huge DNA text ( $∣Σ∣ = 4$ ) aur ek lamba DNA pattern hai. Kya tum expect karoge ki Boyer-Moore ka sublinear best case strongly kick in karega? English text search se ya connections list ke kisi alternative algorithm se compare karo.

Recall Solution

BM ki sublinear speed alphabet size ke saath badhti hai: bada alphabet mismatching text char ko $P$ mein often absent banata hai, jo full-length bad-character jumps trigger karta hai (jaise L2.2 aur L4.1 mein). DNA mein sirf 4 symbols hain, isliye "absent character" rare hai — almost har text char $P$ mein bhi hota hai, toh bad-character jumps usually chhote hote hain aur good-suffix rule end up mein zyada useful kaam karta hai. BM DNA par bilkul usable hai, lekin uske skips chhote hote hain aur yeh English (26+ letters) ya arbitrary byte data (256 symbols) ke comparison mein kam dramatically sublinear hai, jahan bade absent-char jumps common hain. Connections list ke alternatives: chhote alphabets ke liye ya jab tumhe hard linear guarantee chahiye, prefer karo Knuth-Morris-Pratt (KMP) (strict $O (n)$ , Borders and Prefix Function ke prefix function par built); Z-Algorithm same linear guarantee deta hai bahut clean construction ke saath. Agar tumhe ek saath bahut saare patterns search karne hain, toh Aho-Corasick BM ko repeatedly run karne se behtar hai, aur Rabin-Karp attractive hai jab hashing / multiple-pattern averaging help kare. Short mein: BM tab shine karta hai jab alphabet bada ho aur pattern moderately lamba ho; chhote-alphabet DNA par linear-time competitors aksar zyada safe default hote hain.

L5.3 Prove karo ki bad-character shift $shift_{b c} = max (1, j - last (c))$ koi valid occurrence skip nahi karta jab $last (c) < j$ ho.

Recall Solution

Maano mismatch pattern index $j$ par hai, aur offending text char hai $c = T [s + j]$ , with $r = last (c) < j$ ( $P$ mein $c$ ka rightmost index $r$ hai, $j$ se left mein). Agar $P$ kisi shift $s^{'} > s$ par match kare, toh absolute position $s + j$ par text character (jo $c$ hai) kisi aise pattern index ke saath align hona chahiye jo actually $c$ hold karta ho. Aisa largest index $r$ hai. $P [r]$ ko position $s + j$ ke neeche align karne ke liye $s^{'} = (s + j) - r = s + (j - r)$ chahiye. Koi bhi $s^{'}$ jahan $s < s^{'} < s + (j - r)$ ho, wahan ek non- $c$ pattern index us $c$ ke upar aayega, jo immediate mismatch force karega — toh woh alignments impossible hain. Isliye $j - r$ se jump karna sirf provably-empty alignments ko skip karta hai. $max (1, \cdot)$ sirf forward progress guarantee karta hai jab formula non-positive ho. $■$

L5.4 Ek pattern aur mismatch do jahan good-suffix shift Case 2 (border fallback) se aaye, Case 1 se nahi, aur woh shift compute karo. Explain karo kyun Case 1 fire nahi ho sakta.

Recall Solution

Lo $P = ABABA$ ( $m = 5$ ), indices $0..4$ = A B A B A. Maano scan ne suffix $t = P [2..4] = ABA$ (length 3) match kiya aur $j = 1$ par mismatch hua, $P [1] = B$ . Kyun Case 1 fire nahi ho sakta: humein ABA ki ek aur full copy $P$ ke andar chahiye jo strictly index 4 se pehle khatam ho, aur jiska preceding char $P [1] = B$ se alag ho. ABA ki jedhi aur occurrence $P [0..2]$ hai, lekin yeh index 0 se start hoti hai jiske aage koi preceding character nahi hai, isliye yeh valid strictly-internal Case-1 copy nahi hai. Good suffix ki koi full inner copy qualify nahi karti. Case 2 (border fallback): hum instead $P$ ka longest prefix dhundhte hain jo $t = ABA$ ke suffix ke barabar ho. ABA ke suffixes hain A, BA, ABA. Inme se kaun ABABA ka prefix hai? A ✓, ABA ✓ (prefix ABA), BA ✗. Longest hai ABA, length 3. Shift $= m - 3 = 5 - 3 = 2$ . Yeh pattern ke leading ABA ko us text region ke neeche land karta hai jo ABA se match hua tha, bacha hua sirf ek self-consistent placement. Case 2 yahan bhool jaana matlab tum over-shift karo aur ek real occurrence miss kar do.

Recall Self-check clozes

Bad-character shift jab $c$ $P$ mein absent ho aur mismatch index $j$ par ho ::: $j + 1$ (yaani $j - (- 1)$ ), poora pattern aage slide ho jaata hai. Full-match shift $P = AABA$ ke liye ::: $G [0] = m - border = 4 - 1 = 3$ . Case-2 good-suffix shift ABABA ke liye jab good suffix ABA ho ::: $m - 3 = 2$ ( $P$ ka longest prefix jo good suffix ke suffix ke barabar ho woh ABA hai). What restores $O (n)$ worst case ::: the Galil Rule. Kyun BM DNA par kam sublinear hai ::: sirf 4 symbols hain, isliye absent-character full jumps rare hain.