6 Horspool’s Algorithm

Horspool’s algorithm is presented as a shift-based string searching method that breaks away from the usual left-to-right scanning used by earlier approaches. Instead, it compares the pattern against the text from right to left, so mismatches are discovered quickly and can be used to justify large jumps through the text. The central idea is that the algorithm should fail as early as possible, because an early mismatch often means many characters can be skipped without risking a missed match.

To make those jumps safe, the algorithm builds a bad character shift table before searching begins. For each character in the pattern except the last one, it stores a shift value based on the pattern length and the character’s position, with later occurrences overwriting earlier ones so the rightmost valid alignment is preserved. Characters not found in the pattern receive a default shift equal to the full pattern length, while the last character is ignored to avoid a zero shift that could cause the search to stall in an infinite loop. During execution, the algorithm looks up the mismatching text character in this table and shifts the pattern accordingly.

The chapter shows that this strategy can produce sub-linear average performance when the alphabet is large and mismatches are common, because the pattern often leaps over large portions of the text. That makes Horspool especially useful for natural language text, source code, and some database string searches, where many characters do not appear in the pattern. However, it performs poorly on small-alphabet or highly repetitive data such as binary streams or DNA, since mismatches are more likely to involve characters already present in the pattern, forcing short shifts and reducing the advantage of the heuristic.

Baseline example for text and pattern. The matching starts from behind, and ‘e’ is not equal to ‘c’. A mismatch is already found. We move by 6, and the pattern is found.

The letter ‘d’ in the text is compared with ‘y’ in the pattern as scanning is done from right to left. It’s a mismatch. So, checking the bad character table for the letter ‘d’ from table 6.4, the corresponding shift value is 4. The pattern is shifted by 4, and successfully 4 character comparisons were skipped.

The matching is completed in step 4 in the figure. At step 2, the mismatch occurs and the letter is ‘a’. Checking the bad character table, the value of ‘a’ is 3, and we move forward by 3. At step 3, the mismatch occurs again, and the character is ‘d’ with value 4 from the bad character table, and we move forward by 4. Step 4 is the final step where the pattern is matched.

• The Boyer-Moore-Horspool algorithm represents a fundamental paradigm shift in string matching, abandoning the left-to-right scanning tradition to achieve sub-linear search speeds
• Unlike naive algorithms, Rabin-Karp, or KMP, Horspool physically aligns the pattern with the text but executes its character-by-character comparisons in reverse, starting from the rightmost character of the search window and moving left.
• The algorithm derives its speed not from tracking what matches but by heavily penalizing what does not. It assumes that if a mismatched text character does not exist anywhere in the search pattern, the entire pattern can be safely skipped past that character.
• To instantly calculate these skips in O(1) time, Horspool pre-computes a mathematical shift table before the search begins.
• Every unique character in the pattern is assigned a shift distance using the equation Shift = Length - 1 - index.
• If a character repeats within the pattern, its shift value is continuously overwritten. The table must always store the value of the rightmost occurrence. This mathematically guarantees the algorithm will make the smallest, safest possible shift, completely preventing it from jumping over a valid match.
• The very last character of the search pattern is strictly excluded from the table's construction. If evaluated, it would yield a shift value of 0, creating a fatal infinite loop in the search logic. By ignoring it, the minimum possible shift becomes 1.
• Any text character that does not exist in the shift table is instantly assigned the default maximum shift distance: the total length of the pattern.
• In optimal conditions, Horspool does not evaluate every character in the text. It leaps over massive blocks of data, resulting in an average-case time complexity of O(n/m). Counter-intuitively, the longer the search pattern, the faster the algorithm performs.
• The algorithm thrives on text with massive, diverse alphabets (e.g., standard English, source code, server logs). A large alphabet ensures that mismatches frequently trigger the maximum default shift.
• Because of its aggressive skipping capabilities in static memory, variants of Boyer-Moore-Horspool are the standard underlying engines for relational database substring queries, V8 JavaScript engine operations on long strings, and common desktop search utilities

1. Horspool, R. N. (1980). "Practical fast searching in strings". Software: Practice and Experience. 10 (6): 501–506. CiteSeerX 10.1.1.63.3421. doi:10.1002/spe.4380100608. S2CID 6618295.
2. YouTube: https://www.youtube.com/watch?si=SMZJ2fEtDejKr6u0&v=isK0Qu3XHvo&feature=youtu.be
3. Relation databases application: https://github.com/postgres/postgres/blob/master/src/backend/utils/adt/varlena.c
4. V8 Engine: https://github.com/v8/v8/blob/main/src/strings/string-search.h
5. Code implementation: https://github.com/aniketwattamwar/Algorithms-Every-Programmer-Should-Know

FAQ