Boyer-Moore — bad character, good suffix heuristics: Exercises

Reminders you will use constantly (all from the parent):

Throughout, indices are 0-based: $P [0]$ is the first character, $P [m - 1]$ the last.

The picture below is your mental model for every problem on this page. Keep glancing back at it.

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

Figure s01 — Boyer-Moore alignment. The upper pale-blue row is the text $T$ ; the lower row is the pattern $P$ slid underneath at one alignment. The lavender arrow shows the scan direction: we start at the right end of $P$ and walk left. The mint cells (right portion of $P$ ) are the matched good suffix — they already agreed with the text above them. The single coral cell is the first mismatch; the text character sitting directly above it is the bad character $c$ . The bad-character rule reacts to that coral column; the good-suffix rule reacts to the mint block. Every exercise on this page is one of these pictures with different letters.

Definition The good-suffix array

$G$ — built once, used everywhere Because $G [j + 1]$ and $G [0]$ appear in almost every formula on this page, here is how to construct the whole array $G [0 \dots m]$ so you never have to flip back to the parent.

$G$ has length $m + 1$ . $G [j + 1]$ is the shift to use when the mismatch is at pattern index $j$ (so the matched suffix has length $m - 1 - j$ ). $G [0]$ is the shift used after a full match.
Rule for a full match / whole-pattern shift: $G [0] = m - (length of the longest proper border of P)$ . A border (defined in L1.3) is a string that is both a proper prefix and a proper suffix. This respects self-overlap so you never skip an overlapping occurrence.
Case 1 (the good suffix reappears inside $P$ ): if the matched suffix $t = P [j + 1.. m - 1]$ occurs again earlier in $P$ with a different preceding character, shift so that inner copy lines up under the text — shift $=$ (right end of the matched suffix) $-$ (right end of that inner copy).
Case 2 (only a suffix-of- $t$ survives as a prefix of $P$ ): if no full inner copy exists, align the longest prefix of $P$ that equals a suffix of $t$ ; the shift is $m$ minus that prefix length.

Formula A concrete step-by-step way to fill all of

$G$ A clean two-pass construction (the standard textbook one) computes $G [k]$ for every $k = 0 \dots m$ from the $suff []$ array (defined in L3.1). Here $k = j + 1$ is the length of the matched suffix's start index, and $G [k]$ is the shift when the matched suffix is $P [k .. m - 1]$ .

Initialise $G [k] = m$ for all $k$ (safe default — never skips a match).
Pass A (Case 2, prefix = suffix). Walk $i$ from $m - 1$ down to $0$ . Keep a pointer $lastPrefix$ = the smallest start index seen so far whose suffix is a whole-pattern prefix (i.e. $suff [i] = i + 1$ ). For every $k$ from $0$ up to $m - 1$ not yet overwritten by a stronger rule, set $G [k] = m - lastPrefix$ . This fills positions where only a suffix of the good suffix survives as a prefix of $P$ .
Pass B (Case 1, internal reoccurrence). For $i$ from $0$ to $m - 2$ , let $k = m - 1 - suff [i]$ ; set $G [k] = (m - 1) - i$ . Because we sweep $i$ increasing, later (larger- $i$ , i.e. rightmost) copies overwrite earlier ones with the smallest valid shift — the tightest legal jump.
Full match: $G [0]$ ends as $m - (longest border)$ automatically from Pass A. A fully worked run of this procedure is given in L4.4.

Level 1 — Recognition

L1.1 For $P = NEEDLE$ ( $m = 6$ ), write $last (c)$ for every letter that occurs, and state $last (X)$ .

Recall Solution

Index the pattern: $P [0] = N, P [1] = E, P [2] = E, P [3] = D, P [4] = L, P [5] = E$ . $last (c)$ is the rightmost index at which $c$ appears.

$last (N) = 0$ (only at index 0).
$last (E) = 5$ — E appears at 1, 2, 5; rightmost is 5.
$last (D) = 3$ .
$last (L) = 4$ .
$last (X) = - 1$ — X does not occur, so we return the "not present" sentinel $- 1$ .

L1.2 In Boyer-Moore, which end of the pattern do we compare first, and why?

Recall Solution

We compare the rightmost character $P [m - 1]$ against the text first, then move leftward. Reason: a mismatch near the right tells us a whole matched suffix already lined up. That matched suffix is exactly what the good-suffix rule exploits, and the mismatching text character is what the bad-character rule exploits. If we compared left-to-right (like naive matching) we'd never learn a suffix, and the big skips would be impossible.

L1.3 A "border" of a string is defined how, in one sentence?

Recall Solution

A border is a proper substring (not the whole string) that is simultaneously a prefix and a suffix. Example: in ANANA, the string ANA is a border (it's the first 3 chars and the last 3 chars). This links to Borders and Prefix Function.

Level 2 — Application

L2.1 $P = ABCAB$ ( $m = 5$ ). A mismatch happens at $j = 2$ (so $P [2] = C$ ) and the text character there is $c = B$ . Compute $shift_{b c}$ .

Recall Solution

$last (B)$ in ABCAB: B occurs at indices 1 and 4, so $last (B) = 4$ . $shift_{b c} = max (1, j - last (B)) = max (1, 2 - 4) = max (1, - 2) = 1$ . The raw formula gave $- 2$ (would shift backward!), so the $max (1, \cdot)$ clamp saves us. Here the bad-character rule is weak; in a real run the good-suffix rule would supply the real jump.

L2.2 Same $P = ABCAB$ , mismatch at $j = 4$ (comparing the last char) with text char $c = Z$ . Compute $shift_{b c}$ .

Recall Solution

$last (Z) = - 1$ (Z is absent). $shift_{b c} = max (1, 4 - (- 1)) = max (1, 5) = 5$ . Because Z is nowhere in $P$ , we slide the entire pattern past that text position — a jump of the full pattern length. This is the sublinear magic in action.

L2.3 $P = TATAT$ ( $m = 5$ ). Mismatch at $j = 3$ with text char $c = A$ . Compute $shift_{b c}$ .

Recall Solution

Index: $P [0] = T, P [1] = A, P [2] = T, P [3] = A, P [4] = T$ . $last (A) = 3$ . But the mismatch itself is at $j = 3$ — the bad char aligns with the very index we mismatched at. $shift_{b c} = max (1, 3 - 3) = max (1, 0) = 1$ . The clamp fires again: $j - last (c) = 0$ would mean "don't move," which is illegal. We take $1$ .

Level 3 — Analysis

L3.1 For $P = GCAGAGAG$ ( $m = 8$ ), compute the $suff []$ array, where $suff [i]$ is the length of the longest suffix of $P$ ending at index $i$ that is also a suffix of the whole $P$ .

Recall Solution

Index: $P = G C A G A G A G$ at $0 \dots 7$ . The whole-pattern suffix reads (right to left) G A G A G A C G.

$suff [7] = 8$ by convention (the whole string is a suffix of itself).
$suff [6]$ : suffix ending at 6 is ...A; whole-P ends in G. A≠G → $0$ .
$suff [5]$ : ends at 5 with G; compare G(P[5]) vs G(P[7]) match; A(P[4]) vs A(P[6]) match; G(P[3]) vs G(P[5]) match; A(P[2]) vs A(P[4]) match; P[1]=C vs P[3]=G stop. Length walked over indices 5,4,3,2 → $suff [5] = 4$ .
$suff [4]$ : ends at 4 A vs P[7] G → $0$ .
$suff [3]$ : ends G vs G match; P[2]A vs P[6]A match; P[1]C vs P[5]G stop → $2$ .
$suff [2]$ : A vs G → $0$ .
$suff [1]$ : C vs G → $0$ .
$suff [0]$ : G vs G match, no more chars to the left → $1$ . Result: $suff = [1, 0, 0, 2, 0, 4, 0, 8]$ .

L3.2 $P = ANPANMAN$ ( $m = 8$ ). The good suffix AN (length 2) matched, mismatch at index $j = 5$ (char $P [5] = M$ ). There are two earlier copies of AN, at indices $0 - 1$ and $3 - 4$ . Explain why we must reject one of these copies as a Case-1 candidate, and which copy we actually align.

Recall Solution

Index: $P = A N P A N M A N$ at $0 \dots 7$ . Good suffix is $P [6..7] = AN$ ; mismatch at $j = 5$ , $P [5] = M$ . Case 1 requires the character just before an internal copy of the good suffix to differ from the mismatch char $P [j] = M$ — otherwise sliding to that copy would place the same M in the same relative spot and reproduce the identical mismatch (zero progress).

Reject the copy at $0 - 1$ as a Case-1 candidate: it has no preceding character (it sits at the very start of $P$ ). Case 1 needs a strictly-internal copy with a genuine preceding char to test, so this leading copy is not a Case-1 hit — it only ever contributes through the Case-2 / prefix fallback.
Accept the copy at $3 - 4$ : its preceding char is $P [2] = P$ , and $P \neq = M$ ✓. This is a valid Case-1 copy. So we align the copy at $3 - 4$ under the text's AN. The shift moves the AN at $6 - 7$ to where the AN at $3 - 4$ sits: $shift = 7 - 4 = 3$ . (Had both inner copies been preceded by M, we'd fall through to Case 2 and use a prefix of $P$ instead.)

L3.3 Why is taking $max (shift_{b c}, shift_{g s})$ always safe (never skips a real occurrence)?

Recall Solution

Each rule is derived independently as a guaranteed lower-bound jump: "no valid match can begin anywhere in the skipped region." The bad-character rule proves it using the mismatching text char; the good-suffix rule proves it using the matched suffix. If jump $a$ is safe and jump $b$ is safe, then every alignment strictly below $max (a, b)$ is ruled out by at least one of the two proofs — so $max (a, b)$ is also safe. Taking the larger just means we trust whichever proof reaches further.

Level 4 — Synthesis

L4.1 $P = CCTTTTGC$ ( $m = 8$ ). Compute $last (c)$ for all its letters, then compute $shift_{b c}$ when we align at some $s$ , compare right-to-left, and the first mismatch is at $j = 7$ with text char $c = A$ .

Recall Solution

Index: $P = C C T T T T G C$ at $0 \dots 7$ . $last (C) = 7, last (T) = 5, last (G) = 6, last (A) = - 1$ . Mismatch $j = 7$ , $c = A$ , absent from $P$ : $shift_{b c} = max (1, 7 - (- 1)) = 8$ . We jump the full pattern width, having read only one text character. That's the sublinear behaviour of BM on this alignment.

L4.2 Same $P = CCTTTTGC$ . Now suppose at some alignment $P [7] = C$ matched but $P [6] = G$ mismatched, i.e. $j = 6$ , with text char $c = C$ . Compute both heuristics' shifts and the final BM shift. (For good suffix, the matched suffix is just C; the earlier Cs in $P$ are at indices 0,1,7.)

Recall Solution

Bad character: $c = C$ , $last (C) = 7$ . $shift_{b c} = max (1, 6 - 7) = max (1, - 1) = 1$ . Good suffix: matched suffix is $t = C$ (length 1), i.e. $j = 6$ so we want $G [7]$ . We need an earlier copy of C in $P$ whose preceding char differs from the mismatch char $P [6] = G$ , to align under the text's trailing C.

C at index 1: preceding char $P [0] = C \neq = G$ ✓. Align $P [7]$ over the text position currently over $P [1]$ 's target; the shift to bring $P [1]$ 's C to the slot where $P [7]$ 's C sits is $7 - 1 = 6$ .
(C at index 0 has no preceding char; index 1 is the nearest valid inner copy, giving the smallest safe good-suffix jump = $6$ .) $shift_{g s} = G [7] = 6$ . Final: $max (shift_{b c}, shift_{g s}) = max (1, 6) = 6$ . This is exactly the scenario the parent warns about: bad char alone gives a feeble $1$ ; good suffix rescues it with $6$ .

L4.3 Trace BM (using $max$ of both heuristics) on $T = AABAACAADAABAABA$ (text length $n = 16$ ), $P = AABA$ ( $m = 4$ ). List the alignments $s$ tried and every reported match. At the mismatches, show what the good-suffix rule contributes as well.

Recall Solution

$P = A A B A$ , indices $0..3$ . $last (A) = 3, last (B) = 2$ , others $- 1$ . Recall $n = 16$ (text length), so the last alignment we may try is $s = n - m = 12$ . Good-suffix array facts we need. The longest proper border of AABA is A (prefix A = suffix A), so the full-match shift is $G [0] = m - 1 = 3$ . At the mismatches below the mismatch is always at $j = 2$ (chars B vs a non-B), so the matched suffix is $t = P [3] = A$ (length 1) and we need $G [3]$ . Where does an earlier A reappear, preceded by a char $\neq = P [2] = B$ ? The A at index 0 is preceded by nothing (leading), the A at index 3 is the matched one itself; the nearest usable earlier A for Case 1 is index 0 via the prefix/Case-2 route. Working it out, $G [3] = 2$ for AABA. So on these mismatches $shift_{g s} = 2$ . Step through, always taking $s \leq n - m = 12$ :

$s = 0$ : compare $T [0..3] = AABA$ vs AABA → full match. Report $s = 0$ . Shift $= G [0] = 3 \Rightarrow s = 3$ .
$s = 3$ : $T [3..6] = AACA$ . $P [3] = A$ vs $T [6] = A$ ✓; $P [2] = B$ vs $T [5] = C$ ✗ at $j = 2$ , $c = C$ absent. $shift_{b c} = max (1, 2 - (- 1)) = 3$ ; $shift_{g s} = G [3] = 2$ . Final $= max (3, 2) = 3 \Rightarrow s = 6$ . (Here bad char wins, but good suffix independently justified a jump of 2.)
$s = 6$ : $T [6..9] = AADA$ . $P [3]$ ✓; $P [2] = B$ vs $T [8] = D$ ✗ at $j = 2$ , $c = D$ absent. $shift_{b c} = 3$ , $shift_{g s} = 2$ , final $= 3 \Rightarrow s = 9$ .
$s = 9$ : $T [9..12] = AABA$ → full match. Report $s = 9$ . Shift $= G [0] = 3 \Rightarrow s = 12$ .
$s = 12$ : $T [12..15] = AABA$ → full match. Report $s = 12$ . Shift $= 3 \Rightarrow s = 15 > n - m = 12$ . Stop. Matches at $s = 0, 9, 12$ . Alignments tried: ${0, 3, 6, 9, 12}$ — five, versus $13$ for naive.

L4.4 Build the entire good-suffix array $G [0 \dots m]$ for $P = GCAGAGAG$ ( $m = 8$ ), using the two-pass procedure and the $suff$ array from L3.1. Show each pass.

Recall Solution

From L3.1: $suff = [1, 0, 0, 2, 0, 4, 0, 8]$ , $m = 8$ . Init: $G = [8, 8, 8, 8, 8, 8, 8, 8, 8]$ (length $m + 1 = 9$ ). Pass A (Case 2, prefix = suffix). We look for indices $i$ with $suff [i] = i + 1$ (a whole-pattern prefix ends at $i$ ). Checking: $suff [0] = 1 = 0 + 1$ ✓ (prefix G). No other $i$ satisfies it ( $suff [3] = 2 \neq = 4$ , $suff [5] = 4 \neq = 6$ , etc.). So the only surviving prefix has length $1$ , start index $lastPrefix = ?$ — the smallest start is $m - suff [0] = 8 - 1 = 7$ . For every $k$ not yet set by a stronger rule we fill $G [k] = m - lastPrefix = 8 - 7 = 1$ . Concretely this sets the Case-2 default $G [k] = 1$ for the high- $k$ positions the prefix reaches; $G [0] = m - border = 8 - 1 = 7$ . Pass B (Case 1, internal reoccurrence). For $i = 0 \dots m - 2$ , set $k = m - 1 - suff [i]$ and $G [k] = (m - 1) - i$ , sweeping $i$ upward so rightmost copies give the tightest shift:

$i = 0, suff = 1$ : $k = 7 - 1 = 6$ , $G [6] = 7 - 0 = 7$ .
$i = 3, suff = 2$ : $k = 7 - 2 = 5$ , $G [5] = 7 - 3 = 4$ .
$i = 5, suff = 4$ : $k = 7 - 4 = 3$ , $G [3] = 7 - 5 = 2$ .
(indices with $suff = 0$ give $k = 7$ , harmlessly overwritten toward $m$ .) Result (one standard convention): $G = [7, 8, 8, 2, 8, 4, 7, 8, \dots]$ with the Case-2 fills of $1$ applied to the untouched high positions. The two shifts you actually use most are $G [0] = 7$ (full-match jump) and the Case-1 entries $G [3] = 2, G [5] = 4, G [6] = 7$ . The key competency: you can now derive any $G [k]$ from $suff$ rather than guess it.

Level 5 — Mastery

L5.1 Construct the classic worst case where basic Boyer-Moore degrades to $O (nm)$ , and explain why both heuristics fail to help. Then state what fixes it.

Recall Solution

Take $P = AAAA$ ( $m = 4$ ) and $T = AAAA...A$ ( $n$ copies of A). At every alignment, the right-to-left scan matches all the way to $j = 0$ (no mismatch inside), so we do $m$ comparisons per alignment. There are about $n - m + 1$ alignments. Total $\approx (n - m + 1) \cdot m = O (nm)$ . Why the heuristics don't save us: the good-suffix full-match shift is $G [0] = m - border = 4 - 3 = 1$ (longest proper border of AAAA is AAA, length 3). Bad-character also gives tiny shifts because every char equals A. So we crawl forward by 1 each time while re-reading matched characters. The fix: the Galil Rule remembers how far the previous match reached and skips re-comparing that region, restoring guaranteed $O (n)$ .

L5.2 You have a huge DNA text ( $∣Σ∣ = 4$ ) and a long DNA pattern. Would you expect Boyer-Moore's sublinear best case to kick in strongly? Contrast with searching English text or with an alternative algorithm from the connections list.

Recall Solution

BM's sublinear speed grows with alphabet size: a large alphabet makes the mismatching text char often absent from $P$ , which triggers full-length bad-character jumps (like L2.2 and L4.1). DNA has only 4 symbols, so "absent character" is rare — nearly every text char also lives in $P$ , so bad-character jumps are usually small and the good-suffix rule ends up doing most of the useful work. BM is still perfectly usable on DNA, but its skips are shorter and it is less dramatically sublinear than on English (26+ letters) or arbitrary byte data (256 symbols), where big absent-char jumps are common. Alternatives from the connections list: for tiny alphabets or when you need a hard linear guarantee, prefer Knuth-Morris-Pratt (KMP) (strict $O (n)$ , built on the prefix function of Borders and Prefix Function); Z-Algorithm gives the same linear guarantee with a very clean construction. If you must search many patterns at once, Aho-Corasick beats running BM repeatedly, and Rabin-Karp is attractive when hashing / multiple-pattern averaging helps. In short: BM shines when the alphabet is big and the pattern moderately long; on small-alphabet DNA the linear-time competitors are often the safer default.

L5.3 Prove that the bad-character shift $shift_{b c} = max (1, j - last (c))$ never skips a valid occurrence when $last (c) < j$ .

Recall Solution

Suppose the mismatch is at pattern index $j$ , and the offending text char is $c = T [s + j]$ , with $r = last (c) < j$ (the rightmost $c$ in $P$ is at index $r$ , left of $j$ ). For $P$ to match at some shift $s^{'} > s$ , the text character at absolute position $s + j$ (which is $c$ ) must line up with a pattern index that actually holds $c$ . The largest such index is $r$ . Aligning $P [r]$ under position $s + j$ requires $s^{'} = (s + j) - r = s + (j - r)$ . Any $s^{'}$ with $s < s^{'} < s + (j - r)$ would place a non- $c$ pattern index over that $c$ , forcing an immediate mismatch — so those alignments are impossible. Hence jumping by $j - r$ skips only provably-empty alignments. The $max (1, \cdot)$ merely guarantees forward progress when the formula is non-positive. $■$

L5.4 Give a pattern and mismatch where the good-suffix shift comes from Case 2 (border fallback), not Case 1, and compute that shift. Explain why Case 1 cannot fire.

Recall Solution

Take $P = ABABA$ ( $m = 5$ ), indices $0..4$ = A B A B A. Suppose the scan matched the suffix $t = P [2..4] = ABA$ (length 3) and mismatched at $j = 1$ , $P [1] = B$ . Why Case 1 cannot fire: we need another full copy of ABA inside $P$ ending strictly before index 4, preceded by a char $\neq = P [1] = B$ . The only other occurrence of ABA is $P [0..2]$ , but it starts at index 0 with no preceding character, so it is not a valid strictly-internal Case-1 copy. No full inner copy of the good suffix qualifies. Case 2 (border fallback): we instead align the longest prefix of $P$ that equals a suffix of $t = ABA$ . The suffixes of ABA are A, BA, ABA. Which of these is a prefix of ABABA? A ✓, ABA ✓ (prefix ABA), BA ✗. The longest is ABA, length 3. Shift $= m - 3 = 5 - 3 = 2$ . This lands the pattern's leading ABA under the text region that matched ABA, the only self-consistent placement left. Forgetting Case 2 here would make you over-shift and miss a real occurrence.

Recall Self-check clozes

Bad-character shift when $c$ is absent from $P$ and mismatch at index $j$ ::: $j + 1$ (i.e. $j - (- 1)$ ), sliding the whole pattern past. Full-match shift for $P = AABA$ ::: $G [0] = m - border = 4 - 1 = 3$ . Case-2 good-suffix shift for ABABA with good suffix ABA ::: $m - 3 = 2$ (longest prefix of $P$ equal to a suffix of the good suffix is ABA). What restores $O (n)$ worst case ::: the Galil Rule. Why BM is less sublinear on DNA ::: only 4 symbols, so absent-character full jumps are rare.