Horspool Bad-Character Search

The Horspool algorithm (often considered a simplified version of the Boyer-Moore algorithm) uses an aligned bad-character shift to skip impossible pattern positions. By comparing characters from right to left at each alignment, and shifting based on the text character that aligns with the last position of the pattern, it can achieve sublinear performance in practice.

Worked Example

Let us search for the pattern "abcd" (length m=4) within the text "abcxabcd". First, we construct the bad-character shift table. The default shift is m=4. We iterate through the pattern from left to right, up to the second-to-last character (indices 0 to m-2), and set shift[c] = m - 1 - i.

Pattern: "abcd", m=4
Default shift: 4

Table construction (for i = 0 to 2):
i=0, c='a': shift['a'] = 4 - 1 - 0 = 3
i=1, c='b': shift['b'] = 4 - 1 - 1 = 2
i=2, c='c': shift['c'] = 4 - 1 - 2 = 1

Any other character (like 'd' or 'x') gets the default shift of 4.

Search Trace:
Text:    abcxabcd
Pattern: abcd
         ^--- Rightmost text char is 'x' (at index 3).

Compare right-to-left:
Text 'x' vs Pattern 'd': Mismatch!
Shift by shift['x']: 'x' is not in table, so shift = 4.

Next alignment:
Text:    abcxabcd
Pattern:     abcd
             ^--- Rightmost text char is 'd' (at index 7).

Compare right-to-left:
Text 'd' vs Pattern 'd': Match!
Text 'c' vs Pattern 'c': Match!
Text 'b' vs Pattern 'b': Match!
Text 'a' vs Pattern 'a': Match!

Full match found at index 4!
Shift by shift['d'] for next alignment. 'd' not in table, shift = 4.
End of text reached.

Experiment

Use the interactive module controls to explore how the bad-character shift rule behaves with different inputs:

Set the Text to "Late" and the Pattern to "abcd". Observe how the rightmost character 'x' causes a full shift of 4, skipping 3 alignments entirely.
Change the Text to "Repeated" and the Pattern to "aa". Notice how the shift is only 1 after each comparison, requiring more alignments to be inspected.
Set the Pattern to "Empty". The pattern matches at all possible positions (0 to length of text) with 0 comparisons.
Adjust the Shift probe control to query the shift table for specific characters (e.g., "a", "b", or "x").

Open the module directly: Horspool Bad-Character Search.

Limitations

While the Horspool algorithm excels on average and with large alphabets (where bad-character shifts are often large), its worst-case time complexity remains O(nm). This occurs when the pattern and text cause small shifts and many character comparisons at each alignment, unlike KMP or standard Boyer-Moore which guarantee linear time in the worst case. Additionally, for very small alphabets, the shift values are frequently 1, reducing the algorithm's advantage over the naive approach. Small text worst cases can still be O(nm); we do not claim unconditional improvement over KMP or naive search.

References

The Horspool algorithm was introduced as a simplification of the Boyer-Moore string matching algorithm, emphasizing the practical efficiency of using just the bad-character heuristic applied to the rightmost aligned character.

Source: Practical fast searching in strings. R. N. Horspool (1980).

Horspool Bad-Character Search