BOYER-MOORE read the pattern backwards, skip ahead
To find a word in a page, most methods crawl left to right. Boyer-Moore reads the pattern right-to-left and, on a mismatch, jumps the window forward — often past whole stretches of text it never even looks at. A longer pattern makes it faster. Its skip tables are arrays, so it runs in I-13; its natural output is a list of matches.
THE TECHNIQUE bad-character rule: jump on a mismatch
Align the pattern; compare from its right end leftward. On a mismatch, look at the text character that failed: shift the pattern so its last occurrence of that character lines up (or past it entirely if absent). Watch the window leap. live demo
HISTORY & CREDIT two algorithms, one pair of names
“Boyer-Moore” names one two different algorithms by the same pair — this 1977 search AND the 1981 majority vote (dart 016). cited
~1975 / 1977 · Robert Boyer (at SRI) & J Strother Moore (at Xerox PARC) invent right-to-left skipping and publish “A fast string searching algorithm.” Equal, joint credit — a two-lab collaboration, no priority dispute. same year · Knuth, Morris & Pratt publish KMP (1977); it was KMP who first proved the linear bound for the pattern-absent case, not Boyer-Moore. 1979 / 1980 · Galil makes it worst-case linear; Rytter fixes the good-suffix preprocessing, which was buggy as printed in 1977; Horspool strips it to the bad-character rule alone — the variant most greps ship. property · a longer pattern searches faster — the bad-character jump can skip up to the whole pattern length at once.
“Sublinear” is the expected case; the original is O(nm) worst-case when the pattern recurs. two Boyer-Moores
RECOMMEND FOR I-13 skip tables are arrays; matches want a list
The bad-character rule is a lookup array indexed by character — the rightmost position of each symbol in the pattern. On the bounded array with checked indexing, that table and the scan run:
# bad-character table (rightmost index in "MOORE"), then max-shift on a mismatch
# M:0 O:2 R:3 E:4 (others: -1) -> skip = max(1, j - table[c])
Recommend:nothing new for the search itself — the skip tables are bounded arrays of small integers, the scan is indexed reads and single-character equality, all f64-representable. What is slightly awkward is the output: the natural return is a list of match positions (or first-match / −1), so an array-return / multiple-return is the only piece that wants a frontier the box already tracks. Note: unlike the bitwise Bitap/Shift-Or cousin, classic Boyer-Moore needs no bitwise and no bignum — just the array. A clean fit, output aside.