Worked examples — Boyer-Moore — bad character, good suffix heuristics

This is the hands-on companion to the parent note. There we built the two rules; here we drive them through every situation a real text can throw at us. This page is self-contained: every symbol it uses is (re)built below before it is used.

Recall The three numbers you always need

• $j$ ::: the pattern index where the mismatch happened (we compare right to left, so $j$ starts at $m-1$).
• $c=T[s+j]$ ::: the bad character — the text character sitting under the mismatch (recall $s$ is the alignment offset defined just above).
• $\text{last}(c)$ ::: the rightmost index inside $P$ where character $c$ appears, or $-1$ if $c$ never appears.

Bad-character shift: ${\text{shift}}_{bc}=\max (1,j-\text{last}(c))$. Good-suffix shift: ${\text{shift}}_{gs}=G[j+1]$ (the array $G$ is built just below). Total shift: $\max ({\text{shift}}_{bc},{\text{shift}}_{gs})$.

---

Two building blocks we need first

Before any example we must define the two ideas the good-suffix rule leans on: a border, and the good-suffix shift array $G$. We build them from scratch here so nothing on this page is borrowed.

---

The scenario matrix

Every mismatch or full match during a search falls into exactly one of the algorithmic cases A–H below. (Cases I and J are not new cases — they are contexts in which the same A–H logic is exercised; we tag examples with them only to show the rules under realistic pressure.)

Case	Situation	What decides the shift	Danger if you get it wrong
A	Bad char not in $P$ ($\text{last}(c)=-1$)	slide whole pattern past: $j+1$	none — this is the easy big jump
B	Bad char left of $j$ ($\text{last}(c)<j$)	$j-\text{last}(c)\ge 1$	forgetting it exists → too slow
C	Bad char right of $j$ ($\text{last}(c)>j$)	formula goes $\le 0$ → clamp to 1	infinite loop / backward shift
D	Mismatch at the very first compare ($j=m-1$)	no matched suffix yet, so $G[m]$ is small; bad char rules	over-trusting good suffix
E	Good suffix reoccurs internally (Case 1)	align the earlier copy whose preceding char differs	picking a copy with same preceding char → repeat mismatch
F	Only a border of $P$ = suffix of the good suffix (Case 2)	align that border, shift $=m-\text{border}$	forgetting Case 2 → over-shift, miss a match
G	Full match found ($j$ falls below $0$)	shift by $G[0]$	shifting by $1$ wastes work; shifting by $m$ may skip overlaps
H	Degenerate pattern ($P=\text{aaa...}$)	worst case $O(nm)$; Galil rule fixes	thinking BM is always fast

Context tags used below: I = real-world large-alphabet search (DNA), where Case A fires often → sublinear; J = exam-style "which of the two rules wins the $\max$?".

---

Example 1 — Case C then Case A (context I: real-world DNA)

Step 1 — line up and read right-to-left (alignment (i)). $P[7]=\text{C}$; text char is $T_1[7]$. Counting $T_1$ from 0: G C T T C T G C → $T_1[7]=\text{C}$. Match, move to $j=6$. Why this step? BM compares right-to-left; a match peels off a matched suffix.

Step 2 — reach the first mismatch (alignment (i)). $P[6]=\text{G}=T_1[6]$ ✓; $P[5]=\text{T}=T_1[5]$ ✓; $P[4]=\text{T}$ vs $T_1[4]=\text{C}$ → mismatch. So $j=4$, $c=\text{C}$. Why this step? The first disagreement is the decision point.

Step 3 — this is Case C (bad char to the right). $\text{last}(\text{C})$ in CCTTTTGC = index 7. Since $7>j=4$, the naive $4-7=-3$ is illegal (backward). Clamp: ${\text{shift}}_{bc}=\max (1,4-7)=1$. Why this step? Aligning a rightmost copy that lies to the right of the mismatch would drag $P$ backward.

Step 4 — a clean Case A (alignment (ii)). Here $T_2=\text{CCTTATGC}$ at $s=0$. Compare right-to-left: $P[7]=\text{C}=T_2[7]$ ✓; $P[6]=\text{G}=T_2[6]$ ✓; $P[5]=\text{T}=T_2[5]$ ✓; $P[4]=\text{T}$ vs $T_2[4]=\text{A}$ → mismatch at $j=4$, $c=\text{A}$. Character A is absent from CCTTTTGC, so $\text{last}(\text{A})=-1$ and ${\text{shift}}_{bc}=\max (1,4-(-1))=5$ — the Case A jump, skipping characters we never read. Why this step? Case A and Case C are genuinely different; giving each its own concrete text keeps the shift fully reproducible.

Verify: Case C → $\max (1,4-7)=1$. Case A → $\max (1,4+1)=5$. Both positive and legal. ✓

---

Example 2 — Case B (bad char to the left)

Step 1 — locate the bad character. $c=\text{C}$. Why? The text char under the mismatch drives the bad-character rule.

Step 2 — compute $\text{last}(\text{C})$. In A B C A B, the only C is at index 2. So $\text{last}(\text{C})=2$. Why? We want the rightmost copy of $c$ inside $P$ to slide under the mismatch position.

Step 3 — apply the formula. $\text{last}(\text{C})=2<j=3$ → Case B. ${\text{shift}}_{bc}=\max (1,3-2)=1$. Why? A leftward occurrence gives a positive, legal shift — here just 1, small but valid.

Verify: $\max (1,3-2)=1>0$. Aligning index-2 C under text position $s+3$ moves $P$ right by exactly $j-\text{last}(c)=1$. ✓

---

Example 3 — Case C (bad char to the right, clamp)

Step 1 — $\text{last}(\text{A})$. In ABCAB, A appears at 0 and 3; rightmost is 3. Why? Standard bad-character lookup.

Step 2 — compare with $j$. $\text{last}(\text{A})=3>j=2$ → Case C. Why? The rightmost A is right of the mismatch, so the naive formula gives $2-3=-1$.

Step 3 — clamp. ${\text{shift}}_{bc}=\max (1,-1)=1$. Why? A shift of $-1$ moves $P$ leftward, re-reading the same region forever. The $\max (1,\cdot )$ guard prevents this. The good-suffix rule usually supplies a bigger legal jump here.

Verify: $\max (1,2-3)=1$. Without the clamp we'd get $-1$ → non-terminating loop. ✓

---

Example 4 — Case E (good suffix reoccurs, Case 1)

How to read the figure: the top row is ANPANMAN with each character in its own box and its index below. The two red-outlined boxes at indices 6–7 are the matched good suffix AN. The two red boxes drawn below, at indices 3–4, are the earlier internal copy of AN; the black arrow points to its preceding character $P[2]=\text{P}$. The long red arrow shows the pattern sliding right by $6-3=3$ so the earlier AN lands under the already-matched text.

Step 1 — identify the good suffix $t$. $t=P[\mathrm{6..7}]=\text{AN}$ (length $m-1-j=8-1-5=2$). Why? Everything to the right of the mismatch already matched the text; we want to preserve that.

Step 2 — find internal reoccurrences of $t$. As the figure shows, AN sits at indices 0–1 and 3–4. We want one whose preceding character differs from the mismatched $P[j]=\text{M}$. Why? If the preceding char also equalled M, the very next compare would mismatch identically — no progress.

Step 3 — pick the copy at indices 3–4. Its preceding char is $P[2]=\text{P}\ne \text{M}$ ✓. To bring AN from indices 3–4 to where indices 6–7 sit, shift by $6-3=3$. Why? We slide $P$ right so the earlier valid AN lands under the already-matched text.

Step 4 — sanity vs shift-by-1. Shifting by 1 would put $P[7]=\text{N}$ over a text position known to hold A → guaranteed mismatch. So ${\text{shift}}_{gs}=3$ beats 1.

Verify: Case 1 shift $=$ (end index 7) $-$ (earlier copy's end index 4) $=3$, so $G[j+1]=G[6]=3$; matched-suffix length $=2$. ✓

---

Example 5 — Case F (Case 2, border = suffix of the good suffix)

Step 1 — good suffix. $t=P[3]=\text{B}$, length $m-1-j=4-1-2=1$, mismatch at $j=2$. Why? Matched-suffix length $=m-1-j=1$.

Step 2 — Case 1 has nothing usable, so go to Case 2. Why? There is no earlier full copy of B whose preceding character differs in a way that avoids an immediate repeat mismatch; we salvage a partial overlap instead.

Step 3 — find the longest border of $P$. Front reading of ABAB is A,B,…; back reading is B,A,…. The length-2 chunk AB is both the first two and last two characters → border of length 2 (recall the border definition above). Why? The border is the largest overlap between $P$'s start and its own tail, the only alignment that could still match without skipping an occurrence.

Step 4 — shift = $m-(\text{border length})=4-2=2$. Why? Slide so the length-2 border prefix lands where the length-2 border suffix was.

Verify: longest border of ABAB is 2, so Case-2 shift $=m-2=2>0$. A smaller shift only re-examines impossible alignments; a larger one skips the border overlap → could miss a match. ✓

---

Example 6 — Case D (mismatch on the very first compare)

Step 1 — matched suffix length. $m-1-j=6-1-5=0$. Empty suffix. Why? We mismatched before matching anything, so the good-suffix lookup is $G[m]=G[6]$, the entry for an empty matched suffix.

Step 2 — compute $G[6]=G[m]$ cleanly. The good-suffix rule can only ask us to preserve a matched suffix; when that suffix is empty there is nothing to preserve, so the rule imposes no constraint beyond the algorithm's minimum legal move of $1$. Concretely $G[m]=1$: an empty good suffix trivially overlaps at every alignment, so the largest border-of-the-good-suffix that also prefixes $P$ has length $m-1$ (the whole pattern minus one step), giving $m-(m-1)=1$. There is no contradiction — the good-suffix rule simply contributes the neutral value $1$ here. Why? An empty matched suffix carries zero information about where $P$ may next align, so it cannot legally demand a jump larger than $1$.

Step 3 — bad character. $\text{last}(\text{K})$ in NEEDLE $=-1$ → Case A inside Case D. ${\text{shift}}_{bc}=\max (1,5-(-1))=6$. Why? K is absent, so we slide the whole pattern past it.

Step 4 — take the max. $\text{shift}=\max ({\text{shift}}_{bc},G[6])=\max (6,1)=6$. Why? Both rules are valid lower bounds; the larger wins. Here the bad-character rule already hits the maximum possible jump $m=6$, and the neutral good-suffix value $1$ cannot beat it.

Verify: $G[6]=1$; ${\text{shift}}_{bc}=\max (1,5+1)=6=m$; final $\max (6,1)=6$. ✓

---

Example 7 — Case G (full match) + context J (which rule wins)

Step 1 — after a full match, use $G[0]$. With every character matched, $j$ falls to $-1$; there is no bad character to look up, so the shift comes entirely from the good-suffix rule for the whole pattern, which is stored in $G[0]$. Why? No mismatch to trigger the bad-character rule; $G[0]$ tells us the next alignment that could still contain $P$ without skipping an overlapping occurrence.

Step 2 — longest border of ABCAB. Front reading A,B,C,…; back reading B,A,C,…. Test lengths from large to small: length 4 ABCA vs BCAB ✗; length 3 ABC vs CAB ✗; length 2 AB vs AB ✓. So the longest proper border has length 2. Why? The next alignment that can match must reuse the longest self-overlap of $P$ — that is exactly its longest border.

Step 3 — compute $G[0]$. $G[0]=m-(\text{border length})=5-2=3$. After reporting the match we advance $s$ by 3. Why? Shifting by 1 or 2 would place AB… where it cannot re-match; shifting by 4 or 5 could skip an overlapping occurrence beginning inside the just-matched region.

Step 4 — context J twist ($\max$ of the two rules). During a mismatch elsewhere in the same search we always take $\max ({\text{shift}}_{bc},{\text{shift}}_{gs})$. Two illustrative pairs:

• if ${\text{shift}}_{bc}=2$ and ${\text{shift}}_{gs}=3$, the algorithm uses $\max (2,3)=3$ (good suffix wins);
• if ${\text{shift}}_{bc}=5$ and ${\text{shift}}_{gs}=3$, it uses $\max (5,3)=5$ (bad char wins). Why? Each rule is an independently safe lower bound on a legal jump, so the larger is also safe — always compute both and take the max.

Verify: border of ABCAB is 2, $G[0]=5-2=3$. And $\max (2,3)=3$, $\max (5,3)=5$. ✓

---

Example 8 — Case H (degenerate pattern, worst case)

Step 1 — compare each alignment. At every offset $s$, comparing right-to-left, all of $P[2],P[1],P[0]$ equal the text A. We do $m=3$ comparisons, find a full match, and (Case G) shift by $G[0]$. Why? Nothing ever mismatches, so no bad-character skip is ever triggered.

Step 2 — $G[0]$ for AAA. Front reading A,A,…; back reading A,A,…. Longest proper border: length 2 (AA is both first two and last two characters). So $G[0]=m-2=3-2=1$ — we shift by only 1 each time. Why? AAA overlaps itself at every offset, so the only safe post-match move is a single step; a larger jump would skip an overlapping AAA.

Step 3 — count the work. Number of alignments $=n-m+1=8-3+1=6$; each does $m=3$ comparisons and shifts by 1. Total $=6\times 3=18$ comparisons $=O(nm)$. Why? Bad char is useless (every char is A) and good suffix shifts by 1, so BM degrades to the naive $O(nm)$ bound on this input.

Step 4 — the fix. The Galil Rule remembers the already-matched region so it never re-compares it, restoring guaranteed $O(n)$ even here. Related always-linear matchers: Knuth-Morris-Pratt (KMP), Z-Algorithm (both built on Borders and Prefix Function), and hashing-based Rabin-Karp. For many patterns at once, Aho-Corasick.

Verify: alignments $=8-3+1=6$; comparisons $=6\times 3=18$; border of AAA $=2$ so $G[0]=3-2=1$. ✓

---

Recall

Recall Quick self-test

What is the alignment offset $s$? ::: The text position under which $P[0]$ currently sits; $P[i]$ lines up with $T[s+i]$. What is a border of a string? ::: A substring that is both a prefix and a suffix, shorter than the whole string (a proper border). Which case has $\text{last}(c)=-1$? ::: Case A — bad char absent, shift $=j+1$. Which case forces a clamp to 1? ::: Case C — $\text{last}(c)>j$. After a full match you shift by? ::: $G[0]=m-(\text{longest border of }P)$. Case 2 of good suffix fires when? ::: Only a border of $P$ equals a suffix of the good suffix; shift $=m-\text{border length}$. Why take $\max$ of the two rule shifts? ::: Each is an independently safe lower bound, so the larger is also safe and faster.