Horspool算法是Boyer-Moore算法的简化版，同样的，对于这种算法网上的介绍比较详尽，所以这里仅作为简单记录。同Boyer-Moore算法一样，该算法也是基于后缀的字符串匹配算法。不过有所不同的是，Horspool算法认为，Boyer-Moore算法中好后缀表计算所得的跳转距离，大多是少于坏字符表计算所得距离的。所以，在Horspool算法中，就抛弃了好后缀表，仅使用修改过的坏字符表逻辑，来计算跳转距离。相应的，因为抛弃了复杂的好后缀表，Horspool算法的大体效率，是要高于Boyer-Moore算法的。
老规矩，代码实现直接跳转至最后一章。
1. 跳转规则
还是使用模式串FGFAEFG来举例，当匹配情况是这样时:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| X | X | X | X | F | F | G | H | I | J | K | L |
| F | G | F | A | E | F | G |
内容串中，位于模式串末尾位置的字符，是处于第6位置的G。我们把处于这个位置的内容串字符，命名为β。那接下来跳转的距离，就是在模式串中找到β出现的位置，然后把该位置和β对齐，也就是下面这样。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| X | X | X | X | F | F | G | H | I | J | K | L |
| F | G | F | A | E | F | G |
当然了，如果在模式串里找到了多个β，那就取最右侧的位置进行跳转，以避免跳转距离过大，漏掉部分匹配项。
继续匹配，当匹配情况像上面这样时，β就是在内容串中处于第11位置的L，但此时模式串中找不到β了，所以我们就直接跳过整个模式串的距离，像下面这样。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| X | X | X | X | F | F | G | H | I | J | K | L | |||||||
| F | G | F | A | E | F | G |
不过，跳转后模式串已经超出了内容串的范围，所以我们就认为本轮匹配结束了。
所以，总的来说，按照这种跳转规则，来计算模式串对应的跳转表的话，其规则就可以总结成两种情况:
- 1) β能在模式串中找到: 找到模式串中各个不同字符出现的位置，并计算出其和模式串末尾的距离
- 2) β不能在模式串中找到: 跳转距离等于模式串长度
2. 代码实现
Horspool算法的Python封装实现，已经开源上传至github并支持PyPI安装。