参考资料如下：
https://baike.baidu.com/item/Boyer-%20Moore%E7%AE%97%E6%B3%95/16548374?fr=aladdin
https://www.cnblogs.com/ECJTUACM-873284962/p/7637875.html
https://www.jianshu.com/p/87c44a9ffd49
https://blog.csdn.net/qpzkobe/article/details/80716922
文本的窗口滑动还是从左往右。但是
- 每次滑动的距离不再固定是1个字符-根据两个原则计算出来的值决定滑动几个字符长度。
- 每次匹配比较是从右向左比较。即 从尾部开始比较。
下面的术语
搜索词 - pattern
位置指的都是对应的pattern中的位置，位置从0开始计数编号
每次滑动长度计算的两个原则：
- 坏字符原则
后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置
坏字符 即 不匹配的字符。
如果"坏字符"不包含在搜索词之中，则上一次出现位置为 -1。
- 好后缀原则
后移位数 = 好后缀的位置 - 搜索词中的上一次出现位置
好后缀 即所有尾部匹配的字符串。
举例来说，如果字符串"ABCDAB"的后一个"AB"是"好后缀"。那么它的位置是5（从0开始计算，取最后的"B"的值），在"搜索词中的上一次出现位置"是1（第一个"B"的位置），所以后移 5 - 1 = 4位，前一个"AB"移到后一个"AB"的位置。
再举一个例子，如果字符串"ABCDEF"的"EF"是好后缀，则"EF"的位置是5 ，上一次出现的位置是 -1（即未出现），所以后移 5 - (-1) = 6位，即整个字符串移到"F"的后一位。
这个规则有三个注意点：
（1）"好后缀"的位置以最后一个字符为准。假定"ABCDEF"的"EF"是好后缀，则它的位置以"F"为准，即5（从0开始计算）。
（2）如果"好后缀"在搜索词中只出现一次，则它的上一次出现位置为 -1。比如，"EF"在"ABCDEF"之中只出现一次，则它的上一次出现位置为-1（即未出现）。
（3）如果"好后缀"有多个，则除了最长的那个"好后缀"，其他"好后缀"的上一次出现位置必须在头部。比如，假定"BABCDAB"的"好后缀"是"DAB"、"AB"、"B"，请问这时"好后缀"的上一次出现位置是什么？回答是，此时采用的好后缀是"B"，它的上一次出现位置是头部，即第0位。这个规则也可以这样表达：如果最长的那个"好后缀"只出现一次，则可以把搜索词改写成如下形式进行位置计算"(DA)BABCDAB"，即虚拟加入最前面的"DA"。
自我总结：
坏字符移位的本质就是，让text当前位置（从右侧开始匹配的）匹配不上的字符找到pattern中的该字符对应的位置（最近的一个），通过滑动相应的距离（坏字符的位置 - 该字符在pattern中上一次出现位置）让这两个位置对齐。
好后缀移位的本质就是，如果尾部有能匹配上的字符串，（注意肯定是先计算出坏字符移位，因为如果没有坏字符就意味着全匹配上了），出现了坏字符，意味着要移位，但是坏字符移位不一定是 窗口滑动距离最理想的情况，我们可以根据好后缀在pattern中出现的位置，把窗口滑动到 好后缀上一次出现的位置，这个距离可能比坏字符移位距离要大，这样效率更高。
但是这里有两种情况：
-
最长好后缀在pattern中有其他位置重复出现（预处理生成的查找表中很容易得知），选择最近的一个(即最右的)，好后缀的滑动距离由这个计算。
image.png
2.最长好后缀在pattern中的其他位置没有第二个地方出现（预处理生成的查找表中很容易得知）；这意味着此时文本窗口对应的字符串，只能也只需要在前缀（从左开始的几个字符）里找最长好后缀的部分后缀，如果找到，把这重复的部分好后缀对齐，如果找不到子串匹配，意味着前面都对齐不了，公式中的搜索词中的上一次出现位置视为-1（有的帖子把这种情况列为第三类情况）。
image.png
好后缀相当于利于了pattern自身 字符子串的重复循环特性，如果后缀有在pattern中其他地方重复，意味在有好后缀但是整个pattern比对不过的时候，把pattern整体右移至下一次重复部分对齐的位置。
BM算法的精华就在于BM(text, pattern),也就是BM算法当不匹配的时候一次性可以跳过不止一个字符。即它不需要对被搜索的字符串中的字符进行逐一比较，而会跳过其中某些部分。通常搜索关键字越长，算法速度越快。它的效率来自于这样的事实：对于每一次失败的匹配尝试，算法都能够使用这些信息来排除尽可能多的无法匹配的位置。即它充分利用待搜索字符串的一些特征，加快了搜索的步骤。
BM算法实际上包含两个并行的算法（也就是两个启发策略）：坏字符算法（bad-character shift）和好后缀算法（good-suffix shift）。这两种算法的目的就是让模式串每次向右移动尽可能大的距离。这两个算法是“并行”的，哪个对应的移动距离大就用哪个。
通过上面的分析可知，该算法仅需要对pattern字符串 进行预处理， 而不是被搜索的文本字符串。通常搜索关键字越长，算法速度越快。它的效率来自于这样的事实：对于每一次失败的匹配尝试，算法都能够使用这些信息来排除尽可能多的无法匹配的位置。
S[i]为字符串S从1开始排列的第i个字符
S[i..j]为字符串S的一个子串，始于i，终于j。
S的前缀定义为S[1..i],1<i<n，n为字符串S的长度。
S的后缀定义为S[i..n],1<i<=n，小于字符串S的长度。
检索的字符串称为pattern，用符号P表示。
被检索字符称为text，用符号T表示。
P的长度为n
T的长度为m
k表示P的最后一个字符在T中的位置。
当匹配发生时，P在T中的位置为T[(k-n+1)..k]。
Boyer-Moore算法的关键在于，当P的最后一个字符被比较完成后，我们可以决定跳过一个或更多个字符。如果最后一个字符不匹配，那么就没必要继续比较前一个字符。如果最后一个字符未在P中出现，那么我们可以直接跳过T的P的长度个字符，比较接下来的n个字符。如果最后一个字符出现在P中，那么跳过的字符数需要进行计算（也就是将P整体往后移），然后继续前面的步骤来比较。通过这种字符的移动方式来代替逐个比较是这个算法如此高效的关键所在。
形式化的表述方式为，从k=n开始，也就是P从T的最开始进行比较。紧接着，P的第n个字符和T的第k个字符开始：字符串依次从P的最后一个字符到最开始的字符。结束条件是当比较到达P的最开始（此时匹配完成），或按照规则移动后的字符部匹配发生时。然后，在新的对齐位置重新开始比较，如此反复，直到到达T的结尾。
移动规则是一张恒定的查找表，通过对P的预处理产生。
网友评论