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.
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 and usually wins on ordinary text at the cost of twice the preprocessing machinery.
Horspool sits deliberately below all three in sophistication — one table, one fixed lookup, no
positional reasoning about the pattern at all — and gets most of Boyer-Moore's practical speed on
non-adversarial text anyway, 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 nine exact-match entries.