Visual walkthrough — Boyer-Moore — bad character, good suffix heuristics
Step 1 — What are we even doing? Text, pattern, alignment
WHAT. We slide underneath and check "does the pattern sit here?"
WHY. Every string-matching algorithm is this same sliding game — Knuth-Morris-Pratt (KMP), Rabin-Karp, all of them. They differ only in how far they slide each time. Boyer-Moore's whole trick is sliding far.
PICTURE. The green row is , the blue row is placed at shift (meaning sits under ). The little arrow shows that lines up with .
Step 2 — Why compare from the RIGHT?
WHAT. Instead of checking first like a human reading left-to-right, we start at the last character and walk backwards.
WHY. A mismatch discovered near the right end proves the whole tail already matched. Knowing a matched tail (a suffix) is what lets us skip huge distances. If we compared left-to-right we would only ever learn about a matched head, which is far less useful for the jump.
PICTURE. The red pointer starts at the right and moves left. Green cells are equal (); the first red cell is the mismatch.
Step 3 — The one question the bad character asks
WHAT. We look for a inside the pattern to line up with the in the text.
WHY. If we can align a matching under , that slot is no longer guaranteed to fail. Any alignment that puts a non- pattern letter over the text is doomed, so we may skip straight past all of them.
PICTURE. The text's is fixed (yellow). Inside we highlight every position that also holds ; the arrows show the candidate slides.
Step 4 — Which in ? The rightmost one to the left
WHAT. Among all the 's in , we choose the rightmost one whose index is less than .
WHY. Picking the rightmost such gives the smallest safe slide — we never leap over an alignment that could have matched. (Choosing a further left would slide more, possibly jumping past a real match. We want the largest jump that is still safe, and the rightmost-to-the-left copy is exactly the boundary.)
PICTURE. Two copies of in ; the green arrow picks the rightmost one left of , sliding it under the text . The greyed-out arrow (a copy right of ) is illegal — it would move the pattern backwards.
Step 5 — Turning the picture into a shift number
WHAT. We derive how far right to slide so that lands under .
WHY. The mismatch is at pattern index ; the target copy is at index . Sliding the pattern right by moves index up to where index used to be.
PICTURE. The bracket measures the gap — that exact number of columns is how far the blue pattern jumps right.
Step 6 — The three signs: positive, zero-or-negative, and the clamp
This is the case-coverage step. The raw shift can be positive, zero, or negative — we must handle all three.
Case A — (copy is to the left). Then : a genuine forward jump. Safe, done.
Case B — (no copy). Then shift : the maximal jump, covered in Step 5.
Case C — (rightmost copy is to the right of the mismatch). Then — the formula wants to slide the pattern backwards or not at all. That is illegal: it would re-examine the same columns forever, an infinite loop.
WHY the clamp. A backwards or zero shift never makes progress. The smallest legal forward move is , so we take the larger of the raw shift and .
PICTURE. Three mini-panels, one per sign. Panel C shows the backwards arrow crossed out and replaced by a shift of exactly .
Step 7 — A fully worked bad-character jump
Step 8 — The second, independent jump: good suffix (sketch)
WHAT. The matched tail (the good suffix ) is known to sit correctly. We slide so that either another internal copy of , or a matching prefix of , re-lands on that already-matched text.
WHY. Bad-character ignores the matched tail completely. The good-suffix rule uses it, and in the weak cases (like Step 7's shift of ) it supplies a much larger legal jump. A border of a string is a proper substring that is both a prefix and a suffix — see Borders and Prefix Function; that idea is what makes the good-suffix table computable.
PICTURE. Top: the good suffix (green) matched. Middle: Case 1 — an internal copy of whose preceding character differs from slides under the text. Bottom: Case 2 — no full internal copy, so a prefix of that equals a suffix of is aligned.
The one-picture summary
The final figure compresses the whole derivation: right-to-left scan finds the mismatch at with bad character ; the bad-character rule pulls the rightmost (clamped to ) forward; the good-suffix rule re-aligns the matched tail; the actual jump is the max of both.
Recall Feynman retelling — say it in plain words
Line up the short pattern under the long text. Start checking from the right end and walk left. The moment two letters disagree, look at the text letter that broke it — call it . Ask: "is there a somewhere earlier in my pattern I could slide over to here?" Slide the rightmost such into place — that's columns. If there's no at all, jump the whole pattern past it. If the only sits to the right of the break, that slide would go backwards, so just nudge by one instead. Meanwhile, the tail you already matched is precious information too: slide so a repeat of that tail (or a matching front-of-pattern) lands back on it. You have two honest jump numbers; take the bigger one. Because a single failed comparison on the right can license skipping many unread letters, on big alphabets you often read far fewer than characters — that's the sublinear win. Compare this with Knuth-Morris-Pratt (KMP) and the Z-Algorithm, which never skip text but guarantee linear time; the Galil Rule patches Boyer-Moore's worst case to too.
Recall Quick self-test
Raw bad-character shift at mismatch index ? ::: Why clamp with ? ::: to prevent a zero/backward shift (infinite loop) when Shift when ? ::: (via ) Final combined Boyer-Moore shift? :::