liveBook · Manning

Boyer-Moore-Horspool algorithm

As explained in Algorithms Every Programmer Should Know

The Boyer-Moore-Horspool algorithm is a string-search procedure that compares pattern characters from right to left and uses character-based skip distances to shift the pattern.

Suppose you are searching a long document for a word. If a character at the end of the current search window cannot occur in that word, checking the next nearby window would be wasted work. The Boyer-Moore-Horspool algorithm, or Horspool algorithm, uses that mismatch to move the pattern several positions at once. section 6.0

The search has two parts:

  • Prepare a bad character shift table. For a pattern of length m, give each character except the last a shift of m − 1 − its index. Later occurrences overwrite earlier ones; a character absent from the table gets the default shift m. section 6.1 section 6.2
  • Align the pattern with a text window and compare characters from right to left. On a mismatch, use the shift table to advance the window; on a complete match, record its starting position and advance to continue searching. section 6.1 section 6.2

Why the last occurrence wins

For the pattern “abcdabcy,” m is 8. The first “a,” at index 0, suggests a shift of 7; the later “a,” at index 4, replaces that with 3. Likewise, the final table gives “b” 2, “c” 1, and “d” 4. Other characters get 8. Keeping the smaller shift avoids jumping past a possible match. The final “y” is excluded: its calculated shift would be zero, so the search could stop moving. section 6.2 section 6.5

Table 6.3 Step-by-step bad character table construction for ‘abcdabcy’
Index (i)
character (pattern[i])
Shift = Length - 1 - index
Action taken
Current table state
initial
-
-
Default shift
[Default: 8]
0
a
8-1-0=7
Add new character
[a: 7]
1
b
8-1-1=6
Add new character
[a: 7, b: 6]
2
c
8-1-2=5
Add new character
[a: 7, b: 6, c: 5]
3
d
8-1-3=4
Add new character
[a: 7, b: 6, c: 5, d: 4]
4
a
8-1-4=3
Overwrite previous ‘a’
[a: 3, b: 6, c: 5, d: 4]
5
b
8-1-5=2
Overwrite previous ‘b’
[a: 3, b: 2, c: 5, d: 4]
6
c
8-1-6=1
Overwrite previous ‘c’
[a: 3, b: 2, c: 1, d: 4]
7
y
-
Ignore final character
[a: 3, b: 2, c: 1, d: 4]

Follow the table row by row to see later occurrences replace earlier shift values. section 6.2

Horspool can be fast when a pattern is searched in text already in memory, especially when the text has many different characters: characters absent from the pattern permit full-length jumps. The tradeoff is preprocessing the table. Short patterns may not repay that cost, while repetitive text or a small alphabet can force tiny shifts. Its worst-case search time is O(n × m), where n is text length; the favorable skipping behavior is described as approximately O(n/m). Unlike KMP’s approach to continuous streams, Horspool relies on access to the current text window. section 6.3 section 6.4

How Algorithms Every Programmer Should Know covers it

How deep it goes
Works through shift-table construction, repeated characters, right-to-left search, pseudocode, Python implementation, and performance tradeoffs.
Examples
Traces shift tables for “aabadc” and “abcdabcy,” including repeated characters and a right-to-left match.
What it assumes
Assumes familiarity with text-and-pattern matching, while building the bad character shift table step by step.
What you can do after
Build it from scratch with a shift table and right-to-left search that records match positions.
How it connects
Contrasts its mismatch-driven shifts with brute-force string matching, Rabin-Karp, and Knuth-Morris-Pratt.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.