BM算法

BM算法的概念：

BM算法也叫做精确字符集算法，它是一种从右往左比较（后往前），同时也应用到了两种规则坏字符、好后缀规则去计算我们移动的偏移量的算法。

1、坏字符规则

基本思路图解：

首先：提供两个字符串分别是文本串、模式串

因为是从右往左开始比较、为什么呢？因为这样的话如果最后一个比较不上前面的一定就可以不用比较了。
这时：c、d不匹配。所以文本串中的d是坏字符。

利用公式计算出后移位数

后移位数=怀字符的位置-模式串中上一次出现的位置

所以计算结果是：
6=5-（-1）；
因为按数组下标计算，而且模式串中没有该坏字符，所以是（-1）。

接下来继续比较：
c、b不匹配，坏字符是b，发现模式串中有两个坏字符。
这时选择从右往左第一个出现的，因为如果选择后面的话就容易会造成被有遗漏问题。
结果：
3=5-2，所以右移3位。

好后缀规则

好后缀规则和坏字符规则思路上很相似。如下图所示。

当模式串滑动到图中的位置时，模式串和主串有2个字符是匹配的，倒数第三个字符发生了不匹配的情况。我们把已经匹配的ab叫做好后缀，记做{u}。我们拿它在模式串中进行寻找另一个和{u}相匹配的子串{u}。那我们就将模式串滑动到子串{u}和主串{u}对齐的位置。

如果在模式串中找不到另一个等于{u}的子串，我们就直接将模式串，滑动到主串{u}的后面。因为之前的任何一次往后滑动，都没有匹配主串{u}的情况。不过，当模式串中不存在等于{u}的子串时，我们直接将模式串滑动到{u}的后面，这样是否会错过可能匹配的情况呢。如下所示，这里的ab是好后缀，尽管在模式串中没有另一个相匹配的子串{u*}，但如果我们将模式串移动到{u}的后面，那就错过了模式串和主串相匹配的情况

错误情况

所以，当模式串滑动到前缀与主串中{u}的后缀有部分重合的时候，并且重合的部分相等的时候，就有可能会存在完全匹配的情况。针对这种情况，我们不仅要看好后缀在模式串中，是否存在另一个匹配的子串。我们还要考察好后缀的后缀子串，是否和模式串的前缀子串相匹配。

这里我们再来解释一下字符串的后缀子串和前缀子串。所谓字符串A的后缀子串，就是最后一个字符跟A对齐的子串，比如，字符串abc的后缀子串是c、bc。所谓的前缀子串，就是起始字符和A对齐的子串。比如，字符串abc的前缀子串是a、ab。我们从好后缀子串中，找一个最长并且能和模式串前缀子串匹配的，假如是{v}。然后滑动到如图所示的位置。