Intuition The ONE core ideaBoyer-Moore searches for a small pattern inside a big text by lining the pattern up under the text and comparing characters from the right end backwards . The magic is that a single mismatch near the right tells you so much about where the pattern cannot fit that you can leap forward many positions at once — often without even reading most of the text.
Before you can understand the two clever "skip" rules (bad character and good suffix) in the parent note , you need a rock-solid grip on a handful of symbols and pictures. This page builds every single one from nothing. Read it top to bottom; each item leans on the one above it.
Definition String, character, indexA string is just a row of boxes, and each box holds one character (a letter, digit, or symbol). The index is the label written under each box, and — this is the rule that trips up beginners — counting starts at 0 , not 1.
Look at the figure. The word ABCAB is drawn as five boxes. Under each box is its index: 0, 1, 2, 3, 4. So:
The first box is at index 0
The last box is at index 4
Intuition Why index-from-zero matters hereBoyer-Moore constantly talks about "the character at index j length m m − 1 not m m − 1
Definition Text and pattern
T text : the long string we are searching inside . Its length is called n P pattern : the short string we are searching for . Its length is called m
Reading a single box: T [ k ] k P [ i ] i
Intuition Picture them as two strips of paperImagine T P
Because P m ≤ n 0 n − m
Definition Alignment / shifts shift s left edge currently sits. So when the pattern is at shift s P [ i ] T [ s + i ]
The figure shows the pattern strip CCTTTTGC placed with its left edge at s = 2 P [ 0 ] T [ 2 ] P [ 1 ] T [ 3 ]
P [ i ] is above T [ s + i ] .
Intuition Why this "+s" bookkeeping mattersEvery comparison in Boyer-Moore is really "does the pattern box P [ i ] T [ s + i ] k s ← s + k k
Definition Right-to-left comparisonBoyer-Moore does not start comparing at the left (P [ 0 ] rightmost box P [ m − 1 ] leftward (m − 1 , m − 2 , m − 3 , …
WHAT we do: put a finger on P [ m − 1 ] T [ s + m − 1 ] WHY we do it: if we get a mismatch after having matched, say, the last three boxes, we now know the text ends with those three pattern characters. That "known suffix" is exactly the fuel for the big-skip rules. Comparing left-to-right (like naive search) would only ever tell us about a matched prefix , which the skip rules cannot use.WHAT IT LOOKS LIKE : in the figure the green ticks on the right show matched boxes; the red cross shows the first mismatch as we move left.
Definition Mismatch indexj c first box where pattern and text disagree is at pattern index j P [ j ] = T [ s + j ] c = T [ s + j ] bad character .
Everything to the right of j P [ j + 1 … m − 1 ] j not yet checked (except j
In the figure: matched suffix is coloured, the box at index j c
The matched suffix P [ j + 1 … m − 1 ] m − 1 − j j + 1 m − 1
The bad character c P
j Why it feels right: the mismatch happens in the text too.
The fix: j pattern index. The matching text box is found by adding the shift: T [ s + j ]
Intuition Picture: front-chunks and back-chunksTake ABCAB. Its prefixes are A, AB, ABC, ABCA, ABCAB. Its suffixes are B, AB, CAB, BCAB, ABCAB. Notice AB shows up as both a prefix and a suffix — that special coincidence has its own name (next section), and it is the whole heart of the good-suffix rule.
A border of a string is a proper substring (shorter than the whole string) that is simultaneously a prefix and a suffix. "Proper" just means it is not the entire string itself.
Worked example Borders of a wordIn ANPANMAN (length 8):
AN is a prefix (front two boxes) and a suffix (back two boxes) → AN is a border.The empty string is always a trivial border.
Borders answer the question: "if I already matched this back-chunk, where else in the pattern does the same chunk appear so I can reuse the match?" That is precisely Case 2 of the good-suffix rule you'll meet in the parent note. If you want the general machinery behind borders, see Borders and Prefix Function and its cousins Knuth-Morris-Pratt (KMP) and Z-Algorithm .
Definition Last-occurrence functionFor any character c last ( c ) largest index in P c c P last ( c ) = − 1 last ( c ) = { max { i : P [ i ] = c } − 1 c occurs in P c does not occur in P
Intuition Why "-1" and not "0" for absent characters− 1 j − last ( c ) − 1 j − ( − 1 ) = j + 1 whole pattern past the bad spot. If we'd used 0 − 1
Worked example Reading last() off a wordP = ABCAB
last ( A ) = 3 A is box 3),last ( B ) = 4 last ( C ) = 2 last ( Z ) = − 1 Z).
max max ( a , b ) larger of two numbers. max ( 1 , x ) x 1 clamping .
Intuition WHY clamp to 1, and WHY take the max of two rules
Clamp to 1 a shift of 0 1 Max of the two rules: the bad-character rule and the good-suffix rule each independently promise "you will not skip over a real match if you jump this far." When two promises are both safe, the bigger jump is also safe (and faster). So Boyer-Moore takes max ( shift b c , shift g s )
This "each rule is a safe lower bound, take the larger" idea is the logical glue of the whole algorithm — hold onto it when you read the parent's boxed final formula.
Σ Σ ∣Σ∣ ∣Σ∣ ≈ 26 4 A,C,G,T); for bytes it's 256
Intuition Why the alphabet size decides the speedA big alphabet means the bad character c not appear in the short pattern, so last ( c ) = − 1 m m without reading them . Reading fewer than n sublinear " means. On tiny alphabets like DNA the pattern shares many characters with the text, jumps shrink, and the advantage fades. This is why Boyer-Moore shines on large alphabets and why relatives like Rabin-Karp , Aho-Corasick , and the Galil Rule exist for other regimes.
Text T length n, Pattern P length m
Slice notation prefix and suffix
Alignment shift s and T of s plus i
Mismatch index j and bad char c
Border prefix equals suffix
Alphabet size and sublinear
Every foundation box on this page feeds one of the two skip rules, and both rules feed the final search loop — exactly the structure of the parent note.
Test yourself — each line is question ::: answer.
If a string has length m m − 1 0 m − 1
When the pattern is at shift s P [ i ] T [ s + i ]
In which direction does Boyer-Moore compare characters, and why? Right to left, so a mismatch reveals a matched suffix that powers the big-skip rules.
What are j c j pattern index where the first (rightmost-first) mismatch occurs; c = T [ s + j ]
What is a border of a string? A proper substring that is both a prefix and a suffix.
What is last ( c ) c P − 1
Why is the shift clamped with max ( 1 , ⋅ ) To guarantee forward progress — a zero or negative shift would loop forever.
Why does Boyer-Moore take max Each rule is an independently safe jump; the larger of two safe jumps is still safe and faster.
What does "sublinear" mean here and when does it happen? Reading fewer than n P m
🇮🇳 Prefer Hinglish? See 3.8.05 Boyer-Moore — bad character, good suffix heuristics (Hinglish) .
