Boyer-Moore-Horspool
Horspool lines the pattern up, compares from its right-hand end leftwards, and on any mismatch looks at the text character sitting under the pattern’s last position. The shift table says how far that character is from the end of the pattern, and the pattern jumps by exactly that much — which can be the whole pattern length when the character does not appear in the pattern at all.
How far it jumps
Move so the offending character lands where it belongs.
When it is the right choice
This is the one to reach for on ordinary text with a reasonably long pattern and a large alphabet: most characters in English do not appear in a ten-character pattern, so most shifts are the full pattern length and most of the text is never looked at. It degrades to naive search’s worst case on a small alphabet or a repetitive text, and it is a simplification of full Boyer-Moore — one table instead of two — which is why the next page exists.
How it works
- Build a shift table: for every character except the pattern’s last, record how far it sits from the end of the pattern. Everything else shifts by the whole pattern length.
- Line the pattern up and compare its last character against the text beneath it.
- While the characters agree, step left through the pattern.
- If the whole pattern agreed, record an occurrence.
- Either way, look up the text character under the pattern’s last position and shift the pattern by what the table says.
Worth noticing
- The shift is decided by the character under the pattern’s *end*, not by the character that actually mismatched. That is the simplification Horspool makes over full Boyer-Moore, and it is why the table is one-dimensional.
- The skipped counter is the one to watch here: on English text it climbs faster than on any other page, and on the four-letter alphabet scenario it barely moves.
- The last character of the pattern is deliberately left out of the table. Including it would produce a shift of zero and the search would never move.
Cost
- Best
- O(n / m)
- Average
- O(n)
- Worst
- O(n · m)
- Extra space
- O(alphabet)
- Longest text
- 160 characters
- Longest pattern
- 24 characters
The limits are pedagogical rather than technical: one column is drawn per character, and a run has to stay short enough to sit and watch. A text and pattern that would take more than three thousand steps on this algorithm are refused before a single step is generated — and because that depends on the text itself and not only on its length, the tool counts the steps first rather than guessing from a formula.