BM

BM（Boyer-Moore）

BM算法的名字取自于它的两位发明者，计算机科学家Bob Boyer和J Strother Moore。为了能减少比较，BM算法制定了两条规则：

• 坏字符规则（bad character）

• 好后缀规则（good suffix）

坏字符规则

坏字符是指文本串与模式串不匹配的字符。

咦？为什么坏字符不是主串中下标为2的字符T呢？那个位置不是先被检测到吗？

BM算法的检测顺序是从字符串的最右侧向最左侧进行的。当检测到第一个坏字符后，并没有必要让模式串一位一位向后挪动并比较。因为只有模式串与坏字符对齐的位置相同的情况下，两者才有匹配的可能。由于模式串的第1位字符也是T，这样就可以直接把模式串中的T与文本串的坏字符对齐，进行下一轮比较。

坏字符的位置越靠右，下一轮模式串的挪动跨度就可能越长，节省的比较次数也就越多。这就是BM算法从右向左检测的好处。

接着，从右向左成功匹配GCG，并遇到坏字符A。

按照类似的方式，找到模式串的第2位字符A，将它与文本串的坏字符对齐。

如果出现坏字符在模式串中不存在的情况，就直接把模式串挪到主串坏字符的下一位。

好后缀规则

好后缀是指文本串与模式串当中相匹配的后缀。

例如对于这个例子，如果继续使用坏字符规则，模式串只能向后挪动一位。

为了能真正减少比较次数，就需要使用好后缀规则。在第一轮比较中，文本串和模式串都有共同的后缀GCG，这就是所谓的好后缀。如果模式串的其它位置也包含与GCG相同的子串，并且它的前一个字符与原失配位置的模式字符不同，那么就可以挪动模式串，让这个子串与好后缀对齐。

如果模式串中不存在其它与好后缀相同的片段，是不是可以直接把模式串挪到好后缀之后？

使不得！这里还要判断一种特殊情况，模式串的前缀是否和好后缀的后缀相匹配，免得挪过头了。

那应该什么时候用坏字符规则，什么时候用好后缀规则呢？

可以在每一轮字符比较之后，按照坏字符和好后缀规则分别计算相应的挪动距离，哪一种距离更长，就把模式串挪动对应的长度。比如坏字符可以让模式串在下一轮挪动3位，好后缀可以让模式串移动5位，那么就应该采用好后缀规则。