What you're seeing
Most string searches scan left-to-right, one character at a time. Boyer–Moore does two counter-intuitive things that make it the fastest in practice: it compares the pattern right-to-left, and on a mismatch it can jump the pattern forward by many positions at once. The trick is the bad-character rule: when the text character lined up against the pattern doesn't match, look at where that character last appears in the pattern, and slide the pattern so the two line up. If the character appears nowhere in the pattern, slide the whole pattern past it. The longer the pattern and the larger the alphabet, the bigger the skips — the search gets faster as the pattern gets longer.
The rule
last[c] = last index of char c in the pattern (or −1)
s = 0 # alignment of pattern over text
while s ≤ n − m:
j = m − 1
while j ≥ 0 and text[s+j] == pattern[j]: j−− # match right-to-left
if j < 0: report match at s; s += 1
else: c = text[s+j]; s += max(1, j − last[c]) # bad-character skip
The invariant
The skip has to be safe: the bad-character shift never moves the pattern past a real occurrence. Here's why. We mismatched at text character c aligned with pattern position j. For the pattern to match somewhere, some copy of c in the pattern must end up over this text position — and the rightmost such copy is at last[c]. Sliding so that last[c] lands here is the smallest move that could possibly realign; any smaller shift leaves a known-wrong character over c, so it can't be a match. If c never occurs in the pattern, last[c] = −1 and we can skip the pattern entirely past this position. Either way no occurrence is ever stepped over — so the set of matches found is exactly the true set (this entry's test checks that against a brute-force scan).
The cost
On typical text with a reasonable alphabet, the skips average close to m, so Boyer–Moore examines only about n/m characters — sublinear, the rare search that doesn't even read all of its input. The bad-character rule alone can degrade to O(nm) on adversarial inputs (e.g. a small alphabet with many partial matches); the full algorithm adds a second heuristic, the good-suffix rule (reuse the suffix you did match), which together with Galil's rule guarantees worst-case O(n). The simpler Boyer–Moore–Horspool variant keeps only the bad-character rule keyed on the last position, for speed and simplicity.
In the wild
Boyer–Moore (and Horspool) is the workhorse of fast text search: it's the historical core of grep and memmem-style routines, the default in many editors' and languages' substring search, and the intuition behind how tools scan large files quickly. Modern high-throughput searchers (ripgrep, GNU grep) layer SIMD and other tricks on top, but the right-to-left, skip-ahead idea — that you can confirm a non-match by looking at one well-chosen character — is Boyer and Moore's, from 1977.
Try this
Increase the Pattern length and watch the skips grow — longer patterns mean bigger jumps and fewer comparisons (check the readout). Step through a mismatch and read the annotation: it shows the bad character, its last position in the pattern, and exactly how far the pattern leaps. Often several alignments are skipped in a single bound.
References
- Boyer, R. S. & Moore, J S. "A Fast String Searching Algorithm." Communications of the ACM 20(10):762–772, 1977. The original.
- Horspool, R. N. "Practical fast searching in strings." Software: Practice and Experience 10(6):501–506, 1980. The simplified variant.
- Gusfield, D. Algorithms on Strings, Trees, and Sequences, §2 (Exact matching). Cambridge, 1997 — the good-suffix rule and the O(n) bound.