那些经典算法：字符串匹配算法BM算法 _BM算法

单模式串匹配算法中BM（Boyer-Moore）算法算是很难理解的算法了，不过性能高效，据说比KMP算法性能提升3到4倍，suricata里面的单模式匹配就是用这种算法，所以有必要学习下，再把suricata的这部分代码过一下还是不错的。
一、BM算法原理BM算法是1975年发明的,它是一种后匹配算法，我们普通的字符串匹配算法是从左向右的，BM算法是从右向做的，即先判断模式串最后一个字符是否匹配，最后判断模式串第一个字符是否匹配。
原来我们在BF算法中，如果模式串和主串不匹配，则将主串或模式串后移一位继续匹配，BM算法根据模式串的特定规律，将后移一位的步子迈的更大一些，后移几位。来看个图简单说明下，图来自《数据结构与算法之美》课程：

文章插图

但是如果我们仔细观察，c字符在abd中不存在，那么abd可以直接移动到主串中c字符的后面再继续匹配：

文章插图

这样移动的步数变大了，匹配起来肯定更快了。
BM算法根据模式串的特定规律，这里面的特定规律有两种，一种是好后缀规则，一种是坏字符规则，初次看到这种规则的介绍后，心里嘀咕着这性能会好吗，后面才发现经典的BM算法做了不少优化，所以性能高。下面分别介绍下好后缀规则（good suffix shift）和坏字符规则（bad character rule）。
1.1 BM坏字符规则首先在BM算法里面何谓好坏那，匹配上的，我们称为好，匹配不上的叫坏。按照刚才说的，BM算法是倒着匹配字符串的，我们在倒着匹配字符串的过程中，当我们发现某个字符没法匹配的时候，我们把主串中这个没法匹配的字符称为坏字符。

文章插图

我们发现在模式串中，字符c是不存在的，所以可以直接将模式字符串向后滑动3位继续匹配。

文章插图

滑动后，我们继续匹配，发现主串中的字符a和模式串的d不匹配，这时候的情况和上一种不一样，因为主串中的坏字符a在模式串中存在，则后移动2位，让主串和模式串中的a对齐继续匹配。那么每次后移多少位那，我们假设把匹配不到的坏字符的位置记作si，如果坏字符在模式串中存在，则坏字符在模式串中的位置记作xi，那么模式串后移为si-xi；如果坏字符在模式串中不存在，xi就为-1 。上两个图中，第一个图：si = 2，xi = -1 所以后移si-xi = 2+1 =3；第二个图：si = 2，xi= 0所以后移的位置为si-xi=2 。说明下如果坏字符在模式串中存在多个，那么应该选择最后一个匹配坏字符的位置作为xi，这样xi移动的步子就小，就不会遗漏应该匹配的情况。
单纯利用坏字符规则是有问题的，因为si可以为0，xi可能大于0，这样相减为负数，为此BM算法还增加了好后缀规则。
1.2 好后缀规则模式串和主串匹配的部分叫做好后缀，如下图：

文章插图

如上图，我们把匹配的部分bc 叫好后缀，记作{u} 。我们拿它在模式串中查找，如果找到另一个跟{u}匹配的子串{u'},那么我们就将模式串滑动到子串{u'}与主串中{u}对齐的位置。

文章插图

如果在模式串中找不到好后缀，那么直接将模式串滑动到主串中{u}后面，因为前面是没有好后缀的{u}的。

文章插图

但是上面的后移的位数是错误的，这里面有个规则，就是主串中{u}和模式串有重合，模式串移动前缀与主串中{u}第一次重合的部分，这个从直观上来说也是比较好理解的。

文章插图

好后缀规则3
用个示意图标识：

文章插图

说明，某个字符串s的后缀子串，就是最后一个字符和s对齐的子串，比如abc的后缀子串有c和bc 。ab就不是，ab的最后一个字符不对齐；前缀子串，是开头字符跟s对齐的子串，比如字符串abc的前缀子串有a和ab 。我们需要从好后缀的后缀子串中，找一个最长的且跟模式串的前缀子串匹配的，假设是{v},然后将模式串移动到如图位置：