Boyer-Moore combines two shift rules — bad-character
and good-suffix — and takes whichever proposes the larger jump. Nigel Horspool's 1980
simplification keeps Boyer-Moore's right-to-left comparison but throws the good-suffix rule
away entirely, and even changes what the surviving rule looks at: instead of asking "where does the
character that just mismatched last occur in the pattern?", it always asks "where does the
text character aligned with the pattern's last position last occur?" — a fixed lookup that
doesn't depend on where, or whether, a mismatch happened. One table, one lookup per alignment, no
second rule to build or maintain. On this page's default example, searching
"ALABAMA ALABAMA" for "ALABAMA", that simplicity has a real, measured cost:
Horspool finds both occurrences in 20 character comparisons across 5
alignments, against full Boyer-Moore's 16 comparisons across just 3 —
both still well ahead of naive search's 24 (all three checked below, not just
claimed).
Enter a text and a pattern (up to 30 and 12 characters). Step through: the shift table is built once, up front, from the pattern alone — no text involved yet — then each alignment compares right to left, and every mismatch (or full match) triggers exactly the same lookup: the text character aligned with the pattern's last position, regardless of where the comparison actually stopped. The matched pattern lands in green; a mismatch flashes; the pattern's ghost cells show exactly how far each shift moved it.
Right-to-left comparison is unchanged from full Boyer-Moore — the first character checked at each
alignment is still the pattern's last one. What changes is what happens after a mismatch (or
a full match): instead of asking about the specific character that failed, Horspool always asks about
the fixed text position s + m - 1 — the window's last slot — and looks up how
far that exact character would need to move to line up with the pattern's own last-occurring copy of
itself (excluding the pattern's actual final character, which never gets an entry — see Pitfalls for
why). This is safe by the same lower-bound argument as the bad-character rule: if the character
sitting in the text's window-end slot doesn't reoccur anywhere earlier in the pattern, no alignment
that keeps that text position covered could ever match, so the whole pattern can jump past it; if it
does reoccur at some pattern index p, no smaller shift could align a real match either,
since any shift smaller than (m - 1) - p would place a known-different character where
p's copy needs to go.
What's lost by fixing the lookup position: information about where exactly a mismatch
happened. On this page's default example, after finding the match at s = 0, full
Boyer-Moore's good-suffix rule recognizes that "ALABAMA" has no shorter self-overlap — no
proper prefix equals a proper suffix — so no alignment between s = 1 and s = 5
could possibly match, and it jumps straight to s = 6. Horspool has no mechanism that
reasons about the pattern's own internal structure that way; it only ever asks about one fixed text
position per alignment. Its table says shift['A'] = 2 (from 'A''s last
occurrence within pat[0..5], index 4), so it advances by 2 every time regardless — landing
on s = 2, s = 4, then s = 6, redoing a mismatch at pattern index
5 on each of the first three, before finally reaching the second real match at s = 8. Same
correct answer, five alignments instead of three.
This is the exact scheme the demo above steps through — one shift table, then the search:
function shiftTable(pat) {
const m = pat.length;
const table = {};
for (let i = 0; i < m - 1; i++) table[pat[i]] = m - 1 - i; // stop at m-2 — pat[m-1] never gets an entry
return table; // later i overwrites earlier — last wins
}
function horspoolSearch(text, pat) {
const n = text.length, m = pat.length;
if (m === 0 || m > n) return [];
const table = shiftTable(pat);
const matches = [];
let s = 0;
while (s <= n - m) {
let j = m - 1;
while (j >= 0 && pat[j] === text[s + j]) j--;
if (j < 0) matches.push(s); // full match — j walked all the way to -1
const lastChar = text[s + m - 1]; // always this fixed position —
const shift = table.hasOwnProperty(lastChar) // never the character that mismatched
? table[lastChar]
: m;
s += shift;
}
return matches;
}
Building the table over all m pattern positions instead of stopping at
m - 2 corrupts the entry for the pattern's own last character to 0 — and
that entry gets looked up on every single full match, so the bug isn't rare, it's guaranteed to
trigger. Checked directly: for pat = "ab", the correct table (looping
i from 0 to m - 2 = 0) is { a: 1 } — 'b'
gets no entry, so a text ending in 'b' falls through to the default shift of m.
Loop i all the way to m - 1 = 1 instead, and the last iteration overwrites
nothing — it adds table['b'] = m - 1 - 1 = 0. Searching text = "cb":
the single alignment mismatches at pat[0] 'a' vs text[0] 'c', then looks up
text[s + m - 1] = text[1] = 'b' — with the buggy table, shift 0. The window
never moves. Run against the real generator with a 200-iteration safety cap purely to observe the
failure (see this page's build notes): the correct table finishes in 1 alignment and
2 comparisons; the buggy one is still stuck at s = 0 after all 200
capped iterations, having made 400 identical comparisons and advanced nowhere. Excluding the pattern's
final character from the table isn't an arbitrary detail — it's the only thing standing between this
algorithm and a shift of zero.
Looking up the character that actually mismatched — the natural instinct, since that's
what full Boyer-Moore's bad-character rule does — instead of always text[s + m - 1],
doesn't just shift a different amount, it silently skips real matches. Checked:
pat = "AAAA" against text = "DAAAAA". The correct algorithm's only table
entry is { A: 1 }. At s = 0, the right-to-left scan matches the pattern's
other three positions first (text[3..1] are all 'A') before finally
mismatching at pat[0] 'A' vs text[0] 'D' (j = 0); the correct
rule still looks up the window's last character, text[3] = 'A', giving shift 1
— landing on
s = 1, a real match, then s = 2, another real match, for matches
[1, 2]. The buggy version looks up the character that actually failed —
text[0] = 'D', which has no table entry — and gets the default shift of m = 4.
That jumps clean over both real occurrences at s = 1 and s = 2 in one move;
with n - m = 2, the loop is already over. Buggy result: [], zero matches
found in a text that plainly contains two. The fixed lookup position isn't a simplification detail —
it's the only reason the safety argument in "Why it works" applies at all; substituting the mismatch
position invalidates the proof, not just the constant factor.
Dropping the good-suffix rule doesn't just cost a few extra alignments on favorable text —
on the same periodic worst case that defeats full Boyer-Moore, it gives up the shift rules' advantage
entirely and degrades to exactly naive search's comparison count, not just "close to it."
Searching a thousand-character run of 'a' for a ten-character run of 'a':
naive search and full Boyer-Moore (without Galil's rule, per that page's own Pitfalls) both take
9,910 comparisons on this input. Horspool's single-table implementation, checked the same
way, also takes exactly 9,910 — not fewer. The reason is sharper here than for
full Boyer-Moore: every character in both text and pattern is 'a', so the window's last
position is always 'a', the table always returns the same shift of 1, and
the algorithm re-examines the full pattern length at every one of the 991 overlapping
alignments — indistinguishable from the naive algorithm's own behavior on this input, down to the
exact comparison count.
The Complexity section below used to claim, without measuring it, that full Boyer-Moore "usually wins on ordinary text" and that Horspool
merely "gets most of" its speed back. Measured directly: it's backwards, in both of the senses that
claim could mean. Both algorithms' exact reference implementations above were extracted straight out
of this page and boyer-moore.html's own HTML (not reimplemented), instrumented to count
every pat[j] === text[s + j] comparison their scan loop performs, and cross-checked
against naive search on every single trial. Two corpora: a 1.66M-character sample of this site's own
prose (journal.html, tags and entities stripped, lowercased — genuine non-adversarial
English text, not synthetic) and uniform-random lowercase text as a second, structurally different
control. Text lengths 1,000 to 1,000,000, pattern lengths 4/8/16, patterns sampled as real substrings
of the corpus (so most searches actually find something, the realistic case), 40 trials per cell on
the English corpus and 20 on the random control (both measuring comparisons and wall-clock,
not just one), wall-clock taken as the minimum of 5 repeats per trial to damp noise.
text length BM comparisons Horspool comparisons BM wall-clock Horspool wall-clock H/BM
1,000 171 171 0.0075 ms 0.0069 ms 0.91
10,000 1,671 1,689 0.068 ms 0.063 ms 0.93
100,000 16,814 17,028 0.69 ms 0.65 ms 0.93
1,000,000 171,116 173,223 6.98 ms 6.47 ms 0.93
(English corpus, pattern length 8 shown; 4 and 16 move the same direction — see below.) Comparison counts are not a win for full Boyer-Moore anywhere in this measurement: across all 24 size/pattern-length/corpus cells (2 corpora × 4 sizes × 3 pattern lengths), Horspool's comparison count was never lower than full Boyer-Moore's — tied at the low end, up to 4.0% higher at the longest pattern tested. The reason is structural, not a fluke of these two corpora: on text without heavy internal repetition, the good-suffix rule almost never proposes a bigger shift than the bad-character rule Horspool already has on its own, so carrying a second shift rule buys Horspool's single-rule cousin essentially nothing here — the good-suffix rule's real payoff is the periodic worst-case bound this page's own Pitfalls section already measures, not everyday throughput. And because full Boyer-Moore still has to build and consult that second table on every alignment for no comparison-count return, Horspool was faster in wall-clock in every one of the same 24 cells — by roughly 4%-21% at text lengths of 10,000 characters and up (narrower at longer patterns, where more of the total cost sits inside the character-compare loop both algorithms share rather than in per-alignment table bookkeeping); the smallest size tested (1,000 characters, both algorithms finishing in tens of microseconds) shows the same direction but noisier, close to the limits of what a single process's timer can reliably resolve at that scale. "Full Boyer-Moore usually wins on ordinary text" has it backwards twice over: tied-to-slightly-behind on comparisons, and consistently slower in wall-clock, on exactly the non-adversarial text the claim was about.
Time: preprocessing is O(m) for the single shift table — half of full
Boyer-Moore's O(m) + O(m) for two tables, though both are the same asymptotic
class. Search — best/average case O(n/m): on text without heavy internal
repetition, a mismatch on the window's first-checked (last) character against one absent from the
pattern shifts by the full m, the same sublinear behavior full Boyer-Moore gets from its
bad-character rule alone. Search — worst case O(nm), identical to naive
search, not just similar to it: the Pitfalls section's periodic-input example gets the exact same
9,910 comparison count as naive on the same input, because Horspool has neither
Boyer-Moore's good-suffix rule nor a Galil-style overlap tracker to fall back on. Space:
O(min(m, Σ)) for the one table — O(1) beyond that, excluding the match list.
Three other algorithms already on this site solve the same exact-match problem: KMP compares left to right with an unconditional O(n+m)
guarantee that doesn't depend on the alphabet at all; Rabin-Karp skips character comparison almost entirely by
comparing numeric fingerprints; full Boyer-Moore keeps both
shift rules at the cost of twice the preprocessing machinery, which buys back the periodic worst case
(see Pitfalls) but, measured directly, does not win on ordinary text — see measuring ordinary text above. Horspool sits deliberately below all
three in sophistication — one table, one fixed lookup, no positional reasoning about the pattern at
all — and on that same measurement comes out faster in wall-clock on every text/pattern-length
combination tried, not just "most of the way there," which is exactly why simplified real-world
implementations (this is the version most often meant by an unqualified "Boyer-Moore" in library code)
reach for it over the full two-rule algorithm. One more, further removed from all of these: Suffix Array doesn't compare the pattern against the text
at all until query time — it sorts the text's own suffixes once and answers any later pattern with a
pair of binary searches instead of a scan. See Choosing an Exact-Match String
Matcher for how this page compares to the other fifteen exact-match entries.