3.8.5 · D1Boyer-Moore — bad character, good suffix heuristics
Boyer-Moore ek chhote pattern ko ek bade text mein dhundhta hai — pattern ko text ke neeche align karke characters ko right end se left ki taraf compare karta hai. Jaadu yeh hai ki right side ke paas ek akela mismatch itna kuch bata deta hai ki pattern kahan fit nahi ho sakta , ki tum ek baar mein kaafi positions aage kood sakte ho — aksar text ka zyaadatar hissa padhe bina hi.
Pehle tum do clever "skip" rules (bad character aur good suffix) ko parent note mein samajhne se pehle, tumhe kuch symbols aur pictures par pakki pakad chahiye. Yeh page har ek cheez ko scratch se banata hai. Ise upar se neeche padho; har item apne upar wale par tika hua hai.
Definition String, character, indexEk string bas boxes ki ek row hai, aur har box mein ek character hota hai (ek letter, digit, ya symbol). Index woh label hai jo har box ke neeche likha hota hai, aur — yeh woh rule hai jo beginners ko trip karta hai — counting 0 se shuru hoti hai , 1 se nahi.
Figure dekho. ABCAB word ko paanch boxes mein draw kiya gaya hai. Har box ke neeche uska index hai: 0, 1, 2, 3, 4. Toh:
The pehla box index 0
The aakhiri box index 4
Intuition Index-from-zero kyun matter karta hai yahanBoyer-Moore baar baar "the character at index j length m m − 1 m m − 1
Definition Text aur pattern
T text : woh lambi string jiske andar hum search kar rahe hain. Iski length n P pattern : woh chhoti string jise hum dhundh rahe hain. Iski length m
Ek single box padhna: T [ k ] k P [ i ] i
Intuition Inhe kaagaz ki do strips ki tarah sochoSocho T P
Kyunki P m ≤ n 0 n − m
Definition Alignment / shifts Shift s left edge abhi baitha hai. Toh jab pattern shift s P [ i ] T [ s + i ]
Figure mein pattern strip CCTTTTGC ko text strip par s = 2 P [ 0 ] T [ 2 ] P [ 1 ] T [ 3 ]
P [ i ] is above T [ s + i ] .
Intuition Yeh "+s" bookkeeping kyun matter karta haiBoyer-Moore mein har comparison actually "kya pattern box P [ i ] T [ s + i ] k s ← s + k k
Definition Right-to-left comparisonBoyer-Moore comparison left se (P [ 0 ] rightmost box P [ m − 1 ] leftward (m − 1 , m − 2 , m − 3 , …
WHAT karte hain: P [ m − 1 ] T [ s + m − 1 ] WHY karte hain: agar hume mismatch milta hai last teen boxes match karne ke baad, toh hum ab jaante hain ki text un teen pattern characters se khatam hoti hai. Woh "known suffix" exactly woh fuel hai jo big-skip rules ke liye kaam aata hai. Left-to-right compare karna (naive search ki tarah) sirf matched prefix ke baare mein batayega, jo skip rules use nahi kar sakte.WHAT IT LOOKS LIKE : figure mein right side par green ticks matched boxes dikhate hain; red cross woh pehla mismatch dikhata hai jab hum left move karte hain.
Definition Mismatch indexj c pehla box jahan pattern aur text disagree karte hain woh pattern index j P [ j ] = T [ s + j ] c = T [ s + j ] bad character kehlata hai.
j right mein sab already match ho gaya hai: P [ j + 1 … m − 1 ] j abhi check nahi hua (sirf j
Figure mein: matched suffix coloured hai, index j c
Matched suffix P [ j + 1 … m − 1 ] m − 1 − j j + 1 m − 1 Bad character c P
j Kyun sahi lagta hai: mismatch text mein bhi hota hai.
Fix: j pattern index hai. Matching text box shift add karke milta hai: T [ s + j ]
Intuition Picture: front-chunks aur back-chunksABCAB lo. Iske prefixes hain A, AB, ABC, ABCA, ABCAB. Iske suffixes hain B, AB, CAB, BCAB, ABCAB. Notice karo AB dono prefix aur suffix ke roop mein aata hai — is special coincidence ka apna naam hai (agla section), aur yeh good-suffix rule ka poora dil hai.
Ek string ka border ek proper substring (poori string se chhota) hota hai jo simultaneously prefix aur suffix dono hai. "Proper" bas matlab hai yeh poori string nahi hai.
Worked example Ek word ke bordersANPANMAN (length 8) mein:
AN ek prefix hai (front ke do boxes) aur ek suffix bhi hai (back ke do boxes) → AN ek border hai.Empty string hamesha ek trivial border hai.
Borders is sawaal ka jawab dete hain: "agar maine yeh back-chunk already match kar liya, toh pattern mein aur kahan yahi chunk aata hai taaki main match reuse kar sakun?" Yeh precisely good-suffix rule ka Case 2 hai jo tumhe parent note mein milega. Agar tum borders ke peeche general machinery chahte ho, toh Borders and Prefix Function aur iske cousins Knuth-Morris-Pratt (KMP) aur Z-Algorithm dekho.
Definition Last-occurrence functionKisi bhi character c last ( c ) P sabse bada index hai jahan c c P last ( c ) = − 1 last ( c ) = { max { i : P [ i ] = c } − 1 c occurs in P c does not occur in P
Intuition "-1" kyun, "0" kyun nahi absent characters ke liye− 1 j − last ( c ) − 1 j − ( − 1 ) = j + 1 poore pattern ko bad spot se aage slide kar deta hai. Agar hum 0 − 1
Worked example Ek word se last() padhnaP = ABCAB
last ( A ) = 3 A box 3 hai),last ( B ) = 4 last ( C ) = 2 last ( Z ) = − 1 Z nahi).
max max ( a , b ) bada pick karta hai. max ( 1 , x ) 1 clamping kehte hain.
1
1 0 1 Do rules ka max: bad-character rule aur good-suffix rule dono independently promise karte hain "agar tum itna jump karo toh real match miss nahi hoga." Jab do promises dono safe hain, toh bada jump bhi safe hai (aur faster). Isliye Boyer-Moore max ( shift b c , shift g s )
Yeh "har rule ek safe lower bound hai, bada lo" idea poore algorithm ka logical glue hai — jab tum parent note ka boxed final formula padho toh ise pakde raho.
Σ Σ ∣Σ∣ ∣Σ∣ ≈ 26 4 A,C,G,T); bytes ke liye 256
Intuition Alphabet size speed kyun decide karti haiBada alphabet matlab bad character c nahi karta , toh last ( c ) = − 1 m m bina padhe skip kar lete hain. Total n sublinear " kehlata hai. DNA jaisi chhoti alphabets par pattern text ke saath bahut characters share karta hai, jumps chhote ho jaate hain, aur advantage fade hota hai. Isliye Boyer-Moore bade alphabets par chamakta hai aur isliye Rabin-Karp , Aho-Corasick , aur Galil Rule jaisi relatives doosre regimes ke liye exist karti hain.
Text T length n, Pattern P length m
Slice notation prefix and suffix
Alignment shift s and T of s plus i
Mismatch index j and bad char c
Border prefix equals suffix
Alphabet size and sublinear
Is page par har foundation box do skip rules mein se ek ko feed karta hai, aur dono rules final search loop ko feed karte hain — exactly wahi structure jo parent note mein hai.
Khud test karo — har line question ::: answer hai.
Agar ek string ki length m m − 1 0 m − 1
Jab pattern shift s P [ i ] T [ s + i ]
Boyer-Moore characters kis direction mein compare karta hai, aur kyun? Right se left, taaki ek mismatch ek matched suffix reveal kare jo big-skip rules ko power deta hai.
Mismatch par j c j pattern index hai jahan pehla (rightmost-first) mismatch hota hai; c = T [ s + j ]
Ek string ka border kya hota hai? Ek proper substring jo prefix aur suffix dono ho.
last ( c ) c P − 1
Shift ko max ( 1 , ⋅ ) Forward progress guarantee karne ke liye — zero ya negative shift forever loop karega.
Boyer-Moore do rules ke shifts ka max Har rule ek independently safe jump hai; do safe jumps mein se bada bhi safe aur faster hota hai.
"Sublinear" yahan kya matlab hai aur yeh kab hota hai? n P m
🇮🇳 Prefer Hinglish? See 3.8.05 Boyer-Moore — bad character, good suffix heuristics (Hinglish) .
