Boyer-Moore — bad character, good suffix heuristics

Setup & Notation

Text $T$ of length $n$ , pattern $P$ of length $m$ . We want all positions where $P$ occurs in $T$ .
We align $P$ under $T$ at some shift $s$ , then compare $P[m-1]$ vs $T[s+m-1]$ , moving leftward.
On a mismatch (or after a full match) we shift $P$ to the right by some amount and retry.

Heuristic 1 — Bad Character Rule

HOW we derive the shift. We mismatched at pattern index $j$ with text char $c$ . We want to move $P$ right so that the rightmost $c$ in $P$ aligns under position $s+j$ .

If $\text{last}(c) < j$ : that occurrence is to the left of $j$ , so shift = $j - \text{last}(c) \ge 1$ .
If $\text{last}(c) = -1$ : no $c$ in $P$ , shift the whole pattern past it: $j - (-1) = j+1$ .
If $\text{last}(c) > j$ : aligning it would move the pattern backwards — illegal. We clamp to a minimum shift of $1$ .

Heuristic 2 — Good Suffix Rule

HOW we compute it (the $\text{shift\_gs}[\,]$ array indexed by mismatch position $j$ ).

We use two helper arrays. Define $f$ via the standard "Z/border-from-the-right" preprocessing:

Let $\text{suff}[i]$ = length of the longest suffix of $P$ ending at index $i$ that is also a suffix of $P$ : $\text{suff}[i] = \max\{ \ell : P[i-\ell+1 \dots i] = P[m-\ell \dots m-1] \}.$

From $\text{suff}$ we build the good-suffix shift array $G[0\dots m]$ (shift used when mismatch is at index $j$ , i.e. matched suffix length $m-1-j$ ):

Init all $G[\cdot]$ to $m$ (Case 2 default, then refined).
Case 2 (prefix = suffix-of-suffix): for positions where a prefix of $P$ is a border, set those shifts.
Case 1 (internal reoccurrence): for each $i$ where $\text{suff}[i] = i+1$ (i.e. a prefix matches), or wherever $P[i+1\dots]$ reoccurs, record the corresponding shift.

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

Putting it together (search loop)

Formula The 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])

Flashcards

Why does Boyer-Moore compare the pattern right-to-left?

So a mismatch reveals a matched suffix, enabling large skips via the good-suffix rule and aligning the bad text char with its rightmost copy in P.

Define last(c) (last-occurrence function).

The largest index

i

with

P[i]=c

, or

-1

c\notin P

Bad-character shift formula at mismatch index

j

with text char

c

\max(1,\; j-\text{last}(c))

Why the

\max(1,\cdot)

in bad-character shift?

When

\text{last}(c)\ge j

the raw value is

\le 0

(backward/zero shift) → infinite loop; clamp to at least 1.

What is a "good suffix"?

The already-matched suffix

P[j+1\dots m-1]

when mismatch occurs at index

j

Two cases of the good-suffix rule?

(1) Align another internal occurrence of the good suffix whose preceding char differs from

P[j]

; (2) align a prefix of

P

equal to a suffix of the good suffix.

Final BM shift on mismatch?

\max(\text{bad-char shift},\ \text{good-suffix shift})

Why is taking the max of the two shifts safe?

Each rule is an independent valid lower bound on a safe jump; the larger of two safe jumps is still safe.

Best-case and worst-case time of basic BM search?

Best

O(n/m)

(sublinear), worst

O(nm)

; Galil rule makes it

O(n)

Preprocessing cost?

O(m+|\Sigma|)

for bad char,

O(m)

for good suffix.

Recall Feynman: explain to a 12-year-old

Imagine matching a word stamp onto a long sentence. Instead of checking letters left to right, you check the stamp from its last letter backward. The moment a letter doesn't match, you ask two questions: "Where else in my stamp does this wrong letter appear?" (slide so they line up) and "The part that did match — does it appear somewhere earlier in my stamp?" (slide so that lines up too). You then jump by the bigger of the two jumps. Because you sometimes skip whole chunks of the sentence without even looking, it's super fast.

Connections

Knuth-Morris-Pratt (KMP) — also uses borders/prefix-function; good-suffix is its mirror image (suffix borders).
Z-Algorithm — alternative linear preprocessing; relates to computing suff[].
Rabin-Karp — hashing approach; different tradeoff (avg $O(n)$ , no skipping).
Borders and Prefix Function — core theory behind good-suffix Case 2.
Galil Rule — patches BM worst case to $O(n)$ .
Aho-Corasick — multi-pattern matching; BM variants (Commentz-Walter) extend BM ideas.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Boyer-Moore ka core idea ye hai ki naive matching ki tarah pattern ko ek-ek step slide mat karo, aur comparison right se left karo — yaani pattern ke last character se shuru karke peeche ki taraf. Jab koi mismatch aata hai, tab hum do smart rules use karke ek bada jump maar dete hain.

Pehla rule bad character hai: jis text character ne mismatch kiya (use $c$ bolte hain), uska pattern ke andar rightmost occurrence dhoondo aur pattern ko itna slide karo ki wo occurrence us text position ke neeche aa jaye. Agar $c$ pattern me hai hi nahi, to poora pattern us position se aage chhalang maar jata hai — isi wajah se BM kabhi-kabhi text ke saare characters padhta bhi nahi, matlab sublinear speed. Bas dhyan rakho: shift kabhi $\le 0$ na ho, isliye $\max(1,\dots)$ lagana zaroori hai, warna infinite loop.

Doosra rule good suffix hai: mismatch se pehle jo part match ho chuka tha (the matched suffix), wo "achha" hai — use waste mat karo. Pattern ko aise slide karo ki ya to ussi suffix ka ek aur copy pattern ke andar align ho jaye (lekin uske pehle wala character alag hona chahiye, warna same mismatch dobara), ya phir pattern ka koi prefix us suffix ke end se match kar jaye. Dono rules se jo shift aata hai, unme se bada (max) lo — wahi safe aur fast hota hai.

Yaad rakhne ka tareeka: "Right se padho, Bad aur Good me se Bigger jump lo." Yeh algorithm bade alphabets (jaise English text) par KMP se bhi tez chalta hai practical me, isliye grep jaise tools isi family ko use karte hain.

Boyer-Moore — bad character, good suffix heuristics

Setup & Notation

Heuristic 1 — Bad Character Rule

Heuristic 2 — Good Suffix Rule

Putting it together (search loop)

Complexity

Common Mistakes

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — String Algorithms

Connections