Boyer-Moore算法网上的介绍比较多、比较详细，所以这里仅作为简单记录。该算法是基于后缀的字符串匹配算法，相较于KMP算法等基于前缀的算法来说，理论上效率是更高的。但实际上因为其匹配方式，主要是通过坏字符表、好后缀表进行跳转的，而对于很长的，或者缺少回文形式内容的模式串来说，这两个表的计算工作量会很大，所以在特殊情况下并不一定适用。
老规矩，代码实现直接跳转至最后一章。
1. 基于后缀
基于后缀的意思，就是匹配的时候，是从后向前进行匹配的。用模式串FGFAEFG举例子，匹配的时候，是从后往前的，也就是G->F->E->A->F->G->F的顺序。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| F | G | F | A | E | F | A | H | I | J | K | L |
| F | G | F | A | E | F | G |
可以明显的看出，相较于基于前缀的搜索方式来说，这种搜索方式，能更快的确定不匹配情况，所以效率也相对应的更高。
2. 坏字符表
还是用模式串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 |
目前不匹配的字符是第五位字符F，我们称其为坏字符。在模式串中的其他位置，F也是存在的，分别位于第0位和第2位。那么我们取最右侧的F，也就是第2位。移动模式串，使得第2位的F，和刚才内容串中的F相对应，也就是下面这样。
| 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 |
此时我们再从后向前进行匹配，不匹配的字符是I，但模式串里没有I出现，所以我们直接移动模式串的位置越过I，就像下面这样。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| X | X | X | X | F | F | G | H | I | J | K | L | ||||
| F | G | F | A | E | F | G |
这时，因为模式串的位置，已经超出了内容串，所以我们可以认为不再可能匹配到了，因此查找结束。
相应的的，坏字符表的构造方式就清楚了，简而言之就是找出模式串中，每个字符重复出现的位置。跳转的时候，就是移动模式串，使得坏字符能够对应上，刚才找到的其他重复出现的位置。如果找不到，那就直接跃过整个模式串的长度。
3. 好后缀表
还是用模式串FGFAEFG举例子，好后缀规则的情况有两种。
1) 全匹配情况
如果匹配时的情况是下面这样:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| X | X | X | X | X | X | G | H | I | J | K | L |
| F | G | F | A | E | F | G |
已经匹配成功的字符串是G，而在模式串中，G还出现在位置1处，所以此时移动模式串，将位置1处的G，和内容串中的G对齐。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| X | X | X | X | X | X | G | H | I | J | K | L |
| F | G | F | A | E | F | G |
如果匹配时的情况是下面这样:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| X | X | X | X | X | F | G | H | I | J | K | L |
| F | G | F | A | E | F | G |
已经匹配成功的字符串是FG，而在模式串中，FG还出现在位置0处，所以此时移动模式串，将位置0处的FG，和内容串中的FG对齐。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| X | X | X | X | X | F | G | H | I | J | K | L |
| F | G | F | A | E | F | G |
也就是说，这种全匹配的情况，指的是已匹配部分字符串，可以在模式串中的其他位置，完整的找到。此时，就移动模式串，使得已匹配部分字符串，和刚才找到的位置对应。当然，如果已匹配部分，在模式串中存在多处，那就跳转至最右侧那个位置，以免一次性跳转距离太多，漏掉部分匹配结果。
2) 部分匹配情况
如果匹配时的情况是下面这样:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| X | X | X | A | E | F | G | H | I | J | K | L |
| F | G | F | A | E | F | G |
已经匹配成功的字符串是AEFG，但在模式串中，我们再也找不到完整的AEFG了。所以，我们退而求其次，去找已匹配部分AEFG的后缀。AEFG的后缀有EFG、FG、G，但此时我们找的规则有些变化，不是只要出现在模式串中就行，而是必须出现在模式串头部。比如后缀FG和G，都有在模式串中再次出现，FG出现在位置0，G出现在位置1。但因为只有FG出现在模式串头部，所以我们认为AEFG的好后缀是FG。
而此时的跳转，则就是使得刚才找到的好后缀，对齐内容串已匹配部分中的位置。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| X | X | X | A | E | F | G | H | I | J | K | L |
| F | G | F | A | E | F | G |
当然了，除了这两种情况以外，我们可能找不到任何一个完整匹配，或者部分匹配的位置，那么这时我们就直接越过整个模式串的长度。
4. 查找规则
根据上面的介绍，我们可以对模式串进行分析，构造出他的坏字符表和好后缀表两张表。而查找的规则也很简单，就是先通过这两张表计算出各自的跳跃距离，然后取最大值进行模式串移动。
举个例子，根据坏字符表计算出的移动距离是1，根据好后缀表计算出额移动距离是3，那么就取最大值3，使得模式串后移3位。
5. 代码实现
Boyer-Moore算法的Python封装实现，已经开源上传至github并支持PyPI安装。