Question bank — Boyer-Moore — bad character, good suffix heuristics

False. Large alphabets par yeh aksar sublinear hota hai: pattern ke end ke paas ek single mismatch $m$ ka jump force kar sakta hai, to text ke poore runs kabhi inspect hi nahi hote — yahi to poora point hai.

True. Jab $\text{last}(c)\ge j$ ho to raw formula $j-\text{last}(c)$ $\le 0$ hota hai, ek zero ya backward shift; $\max (1,\cdot )$ clamp ke bina alignment kabhi aage nahi badhti.

False. Har rule independently ek safe lower bound hai — koi bhi kabhi match skip nahi karta — to do safe shifts mein se bada bhi safe hai, bas faster.

True. $\text{last}(c)=-1$ ke saath shift hai $j-(-1)=j+1$, $P[0]$ ko offending text char se thoda aage slide karta hai, kyunki $c$ ko overlap karne wala koi alignment kabhi match nahi kar sakta.

False. Right-to-left scanning hi ek matched suffix produce karta hai; good-suffix rule aur "rightmost bad char" logic dono suffix jaanne par depend karte hain, prefix par nahi — ise ulta karo aur skipping logic collapse ho jata hai.

False. Dono cheap hain. Good suffix isliye exist karta hai kyunki adversarial cases mein (jaise bad char kisi late occurrence ke barabar ho) bad-character shift degenerate ho ke $1$ ho jaata hai; good suffix wahan bada legal jump provide karta hai.

False. Yeh $G[0]$ se shift karta hai, poore pattern ke liye good-suffix jump — border ki width batati hai ki $P$ agli baar earliest kahan ho sakta hai, jo usually $1$ se zyada hota hai.

False. $O(n/m)$ best case hai. Basic BM ka worst case $O(nm)$ hai (jaise $P=\text{aaa}$, $T=\text{aaaa}\dots$); Galil Rule ise guaranteed $O(n)$ mein repair karta hai.

True. $P$ mein rightmost $c$ mismatch index ke right mein ho sakta hai; yahi exactly "would move backward" case hai jise $\max (1,\cdot )$ clamp handle karta hai.

False. Yeh ek safe shift guarantee karta hai, lekin Case 1 mein $P$ ko sirf itna slide kiya ja sakta hai ki suffix ki ek internal copy align ho, jo ek chhoti move ho sakti hai; suffix ki length shift par lower bound nahi hai.

Error clamp drop karna hai. Jab $\text{last}(c)\ge j$ ho to yeh $\le 0$ hai; correct rule hai $\max (1,j-\text{last}(c))$ taaki pattern hamesha aage badhta rahe.

Yeh sirf Case 1 hai. Yeh Case 2 bhool jaata hai: jab koi full copy exist nahi karti, to aapko $P$ ka woh prefix align karna hoga jo good suffix ke suffix ke barabar ho. Case 2 skip karne se over-shift hota hai aur real matches miss ho jaate hain.

Nahi — internal copy se pehle wala character differ karna chahiye $P[j]$ se. Agar woh equal hota, to agla comparison wohi mismatch reproduce karta, shift waste ho jaati.

Overlapping matches ke liye galat. $m$ se jump karna ek aisi occurrence se aage nikal sakta hai jo current se overlap karti ho; aapko $G[0]$ se shift karna chahiye, jo pattern ki self-overlap (uski border) respect karta hai. $\text{last}$ ::: bad character ke liye table $O(|\Sigma |)$ extra space bhi cost karta hai, lekin yeh ek memory note hai, is error se alag.

Defining feature iska opposite hai: inner loop $j=m-1$ se start hota hai aur $j$ decrease hota hai. Left-to-right scanning woh suffix knowledge remove kar deti hai jis par har skip rely karta hai.

Nahi. Dono heuristics sirf pattern $P$ (aur alphabet) ko preprocess karte hain. $T$ search phase tak bilkul untouched rehta hai — yahi reason hai ki BM ek $P$ ko kai texts par efficiently handle karta hai.

Taaki ek mismatch peeche ek matched suffix chhhode, jo good-suffix jump unlock karta hai aur bad text char ko $P$ mein uski rightmost copy ke saath align hone deta hai — dono large-skip mechanisms ko suffix information chahiye.

Leftmost copy ke saath align karna $P$ ko itna dur shift kar sakta hai ki woh alignment leap over ho jaye jahan rightmost copy match hoti — woh ek possible match skip kar deta. Leftmost ki taraf rightmost copy sabse bada safe jump hai.

Add karne se over-shift ho sakta hai aur match skip ho sakta hai. Har shift apne reason ke liye separately sabse bada guaranteed-safe move hai; sach mein safe move woh hai jo dono safe reasons mein zyada permit kare, yaani maximum.

Jab bad char $c$ $P$ mein late appear hone wale character ke barabar hota hai (to $\text{last}(c)\ge j$), formula $1$ par clamp ho jaata hai. Yahi exactly woh scenario hai jahan good-suffix rule ko shift rescue karna padta hai.

Kai distinct symbols ke saath, ek random text char ka $P$ mein appear hona unlikely hai, to mismatches frequently "not in $P$" case hit karte hain aur poori pattern width jump karte hain — kai characters unread skip ho jaate hain.

Hum ise guarantee nahi kar sakte. Mismatched text char kisi aisi pattern char ke barabar ho sakta hai jo $j$ ke right mein ho, $\text{last}(c)>j$ ordinary inputs par perfectly possible hai, isliye clamp mandatory hai, defensive fluff nahi.

Jab $P$ aur $T$ ek single repeated symbol share karte hain (jaise sab a), har alignment almost fully match hoti hai phir mismatch hoti hai, $1$ ke tiny shifts aur near-full re-scans dete hain — skips ghaib ho jaate hain. Galil Rule ise fix karta hai.

Almost kuch nahi — sole character se pehle koi non-empty matched suffix nahi hai, to shifts poori tarah bad-character rule se aate hain; BM ek simple "jump to next occurrence" scan mein degenerate ho jaata hai.

Nearly. Distinct characters bad-character shifts ko consistently large banate hain aur degenerate clamp-to-$1$ case rare hota hai, isliye good suffix rarely dominate karta hai — lekin aap dono ko correctness ke liye rakhte hain thode overlap cases mein.

Matched suffix empty hai, to good-suffix rule koi help nahi karta ($G[m]$, iska default); shift purely us pehle char par bad-character rule se aata hai.

Har aisi char ke liye $\text{last}(c)=-1$ hai, to unpar koi bhi mismatch $j+1$ ka maximal bad-character jump trigger karta hai — yahi "foreign" characters hain jo BM ko sublinear banate hain.

Haan, provided post-match shift $G[0]$ use kare (whole-pattern border), jo kabhi overlapping start se aage nahi jump karta; yahi exactly reason hai ki hum blindly $m$ se shift nahi karte.

Good-suffix array apne default $G[j+1]=m$ par fall back karta hai, pattern ko matched region se poori tarah aage slide karta hai — safe hai kyunki $P$ mein kuch bhi iske saath realign nahi ho sakta.

Search loop condition $s\le n-m$ immediately false ho jaati hai, to yeh ek bhi comparison ke bina no matches report karta hai — sahi jawab, kyunki $P$ fit hi nahi ho sakta.