liveBook · Manning

Chapter 6: Horspool’s Algorithm

What you will learn in chapter 6 of Algorithms Every Programmer Should Know

Introduces Horspool’s right-to-left, mismatch-driven approach to string matching and explains why its precomputed shifts can speed up searches.

After this chapter you will be able to

What it builds on

Section by section

Introduction

Introduces Horspool’s right-to-left, mismatch-driven approach to string matching and explains why its precomputed shifts can speed up searches.

Key terms: Horspool algorithm, right to left, mismatches, Bad Character Shift Table, heuristic, mismatch, sub-linear search times

6.1 The paradigm shift: Right to left scanning

This section explains how Horspool’s algorithm compares a pattern from right to left and uses a precomputed bad character shift table to move the pattern safely after a mismatch.

Key terms: right to left, mismatch, bad character, shift, Bad Character Shift Table, Default Shift, Shift = pattern length - 1 - index, overwrite previous character, last character, shift value of zero

6.2 Handling internal redundancy

This section shows how Horspool’s algorithm builds a shift table for a pattern with repeated characters and uses it to skip text alignments during a search.

Key terms: bad character shift table, rightmost occurrence, default maximum shift, bad character, text window, right-to-left, shift, alignment

6.3 Real-World applications

This section explains where Boyer-Moore-Horspool is useful in production and why databases and JavaScript engines may choose it for substring searches.

Key terms: Boyer-Moore-Horspool, large alphabets, static text, Rabin-Karp, KMP, PostgreSQL, strpos(), bad character table, natural language, V8

6.4 Key insights

Explains why Horspool can skip much of a text on average and why its speed depends on the alphabet.

Key terms: right to left, sub-linear, O(n/m), pattern length, alphabet size, bad character, default skip, O(n x m)

6.5 Summary

6.6 References

Lists the original Horspool paper and links to a video, application source code, and an implementation.

Concepts explained in this chapter

← Chapter 5: Knuth-Morris-Pratt Algorithm Chapter 7: Knapsack Algorithm →

These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.