Boyer-Moore — bad character, good suffix heuristics

3.8.5 · Coding › String Algorithms

Setup & Notation

Text $T$ jiska length $n$ hai, pattern $P$ jiska length $m$ hai. Hum woh saari positions chahte hain jahan $P$ , $T$ mein aata hai.
Hum $P$ ko $T$ ke neeche kisi shift $s$ par align karte hain, phir $P [m - 1]$ vs $T [s + m - 1]$ compare karte hain, leftward chalte hue.
Mismatch par (ya full match ke baad) hum $P$ ko right ki taraf kuch amount se shift karte hain aur retry karte hain.

Heuristic 1 — Bad Character Rule

SHIFT DERIVE KAISE KARTE HAIN. Humne pattern index $j$ par text char $c$ ke saath mismatch kiya. Hum $P$ ko right move karna chahte hain taaki $P$ mein rightmost $c$ , position $s + j$ ke neeche align ho.

Agar $last (c) < j$ : woh occurrence $j$ se left mein hai, toh shift $= j - last (c) \geq 1$ .
Agar $last (c) = - 1$ : $P$ mein koi $c$ nahi, poora pattern us se aage slide karo: $j - (- 1) = j + 1$ .
Agar $last (c) > j$ : use align karna pattern ko peeche move kar dega — illegal. Hum minimum shift $1$ tak clamp karte hain.

Heuristic 2 — Good Suffix Rule

ISKO KAISE COMPUTE KARTE HAIN ( $shift_gs []$ array jo mismatch position $j$ se index hota hai).

Hum do helper arrays use karte hain. $f$ ko standard "Z/border-from-the-right" preprocessing se define karo:

Maano $suff [i]$ = $P$ ke longest suffix ki length jo index $i$ par khatam hoti hai aur $P$ ka bhi suffix hai: $suff [i] = max {ℓ : P [i - ℓ + 1 \dots i] = P [m - ℓ \dots m - 1]} .$

$suff$ se hum good-suffix shift array $G [0 \dots m]$ banate hain (shift jab mismatch index $j$ par hai, yaani matched suffix length $m - 1 - j$ ):

Init sabhi $G [\cdot]$ ko $m$ karo (Case 2 default, phir refine karo).
Case 2 (prefix = suffix-of-suffix): jin positions par $P$ ka prefix border hai, wahan shifts set karo.
Case 1 (internal reoccurrence): har $i$ ke liye jahan $suff [i] = i + 1$ (yaani ek prefix match karta hai), ya jahan bhi $P [i + 1 \dots]$ reoccur kare, corresponding shift record karo.

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

Sab kuch ek saath (search loop)

Formula Search algorithm

s = 0
while s <= n - m:
    j = m - 1
    while j >= 0 and P[j] == T[s+j]:
        j -= 1
    if j < 0:
        report match at s
        s += G[0]            # full match: shift by good-suffix of whole pattern
    else:
        c = T[s+j]
        s += max(max(1, j - last[c]), G[j+1])

Complexity

Common Mistakes

Flashcards

Boyer-Moore pattern ko right-to-left kyun compare karta hai?

Taaki mismatch ek matched suffix reveal kare, good-suffix rule se bade skips enable ho aur bad text char ko P mein uski rightmost copy ke saath align kar sakein.

last(c) (last-occurrence function) define karo.

Sabse bada index

i

jahan

P [i] = c

ho, ya

- 1

agar

c \in / P

Mismatch index

j

par text char

c

ke saath bad-character shift formula?

max (1, j - last (c))

Bad-character shift mein

max (1, \cdot)

kyun?

Jab

last (c) \geq j

toh raw value

\leq 0

ho jaati hai (backward/zero shift) → infinite loop; kam se kam 1 tak clamp karo.

"Good suffix" kya hai?

Pehle se matched suffix

P [j + 1 \dots m - 1]

jab index

j

par mismatch hoti hai.

Good-suffix rule ke do cases?

(1) Good suffix ki ek aur internal occurrence align karo jiske pehle wala char

P [j]

se alag ho; (2)

P

ka ek prefix align karo jo good suffix ke suffix ke barabar ho.

Mismatch par final BM shift?

max (bad-char shift, good-suffix shift)

Dono shifts ka max lena safe kyun hai?

Har rule ek independent valid lower bound hai safe jump ke liye; do safe jumps mein se bada bhi safe hai.

Basic BM search ka best-case aur worst-case time?

Best

O (n / m)

(sublinear), worst

O (nm)

; Galil rule ise

O (n)

bana deta hai.

Preprocessing cost?

Bad char ke liye

O (m + ∣Σ∣)

, good suffix ke liye

O (m)

Recall Feynman: 12-saal ke bachche ko samjhao

Socho ek word stamp ko ek lambi sentence par match karna hai. Letters ko left se right check karne ki jagah, tum stamp ko uske aakhiri letter se peeche ki taraf check karte ho. Jaise hi koi letter match nahi karta, tum do sawaal poochte ho: "Mere stamp mein yeh galat letter aur kahan aata hai?" (slide karo taaki woh line up ho jaaye) aur "Jo part match hua — kya woh mere stamp mein kahin pehle bhi aata hai?" (slide karo taaki woh bhi line up ho jaaye). Phir tum dono mein se bade jump se jump karte ho. Kyunki tum kabhi kabhi sentence ke poore chunks skip kar dete ho bina dekhe, yeh super fast hai.

Connections

Knuth-Morris-Pratt (KMP) — borders/prefix-function bhi use karta hai; good-suffix uska mirror image hai (suffix borders).
Z-Algorithm — alternative linear preprocessing; suff[] compute karne se related hai.
Rabin-Karp — hashing approach; alag tradeoff (avg $O (n)$ , koi skipping nahi).
Borders and Prefix Function — good-suffix Case 2 ke peeche core theory.
Galil Rule — BM worst case ko $O (n)$ tak patch karta hai.
Aho-Corasick — multi-pattern matching; BM variants (Commentz-Walter) BM ideas extend karte hain.