关键词规划师/广州seo外包公司

今天，我来学习BM算法。它是一种非常高效的字符串匹配算法，有实验统计，它的性能是KMP算法的3到4倍。初步浏览，BM算法难度不小。要好好搞一波了。

因为太难了，这篇文章参考了王争老师的《数据结构与算法之美》。链接：字符串匹配。就做了一次学习笔记、

8.1 BM算法的核心

我们把模式串和主串的匹配过程，看作模式串在主串中不停的往后滑动。当遇到不匹配的字符时，BF算法和RK算法的做法是，模式串往后滑动一位，然后从模式串的第一个字符重新开始匹配。

举个例子：

在这个例子中，主串的d在模式串中是不存在的，所以，模式串可以向后滑动的时候，只要d与模式串没有重合，肯定无法匹配。所以，我们可以直接一次性把模式串往后多滑动几位，滑动到d的后面。

BM算法，本质上其实就是在寻找这种规律。借助这些规律，能够跳过一些肯定不会匹配的情况，将模式串往后多滑动几位。

8.2 BM算法原理分析

BM算法包含两部分，分别是坏字符规则（bad character）和好后缀规则（good suffix shift）。

8.2.1 坏字符规则

前面两节的算法我们匹配过程中，都是按模式串下标从小到大的顺序，但是这次的BM算法就不是了，它要下标从大到小的顺序，倒着匹配。

从模式串的末尾往前倒者匹配，当发现某个字符没发匹配时，我们把这个没有匹配的字符叫做坏字符。（我们在说算法核心的时候说过）

上图的例子，字符d就是这次的坏字符，然后拿这字符d去模式串中查找，发现模式串中不存在这个字符，所以这时候，包含坏字符d的时候，模式串是都不可能匹配的，所以可以直接跳到d后面，进行再次匹配。（这样效率提高了不少）

然后接下来看下面这种情况，模式串的e还是不能匹配主串的a,这个时候因为a是在子串中的，所以不能直接滑过，需要把模式串中有a的滑到跟主串对齐，然后再从模式串末尾字符开始，重新匹配。

那现在有什么规律呢？看了王争老师写的确实容易理解。

当发生不匹配的时候，我们把坏字符对应的模式串中的字符下标记住si，如果坏字符再模式串中存在，我们就把这个坏字符再模式串中的下标记做xi，如果下标不存在，我们就把xi记做-1，那模式串往后移动的位数等于si-xi。（下标都是模式串中的下标）

是不是不太理解，这就对了，我也是看了3遍才发现了其中的奥秘。

是不是很巧妙，如果怀字符在模式串出现多出，我们的xi选择最靠后那个，这样就不会因为滑太多，导致错过。

坏字符规则也是有局限，下面这个例子就不能用坏字符规则：

主串"aaaaaaaaa"，模式串"baaa"，这个计算出来的si-xi是负数，所以BM算法还要使用到“好后缀规则”。

8.2.2 好后缀规则

好后缀感觉跟坏字符规则思路很类似，我们看看下面的例子:

这时候我们是可以利用坏字符规则，把模式串后移一位，这样模式串中的c就能跟主串中的坏字符c对齐，这时候坏字符规则只移动一位，效率有点低，所以我们来看看好后缀能移动多少位。

1. 我们把已经匹配的bc叫做好后缀，记做{u}，我们拿它在模式串中查找，如果找到了另一个跟{u}相匹配的子串{u*}，那我们就将模式串滑动到子串{u*}与主串{u}对齐的位置。

2. 如果模式串中找不到另一个等于{u}的子串，我们会咋办？可以直接滑到{u}的后面么？有一种情况是不行的，就是模式串滑动到前缀与主串中的{u}有部分重合的时候，并且重合部分相等的时候，就有可能出现完全匹配。

   所以针对这种情况，我们不仅要看好后缀在模式串中，是否有另一个匹配的子串，我们还要考虑好后缀的后缀子串，是否存在跟模式串的前缀子串匹配的。

当模式串和主串中的某个字符不匹配的时候，如何选择用好后缀规则还是坏字符规则，来计算模式串往后移动的位数？

这个我们可以分别计算好后缀和坏字符往后滑动的位数，然后取两个数中的最大值。

这样也可以避免我们前面提到的，坏字符规则会出现负数的情况。

8.3 代码实现

8.3.1 坏字符规则实现

坏字符规则不难的，当遇到坏字符时，要计算往后移动的位数si -xi,怎么求xi呢？我刚开始的想法就是在坏字符模式串中遍历，然后看了王争老师的解法，用哈希直接存储，然后就可以直接获取了，真的是哈希表的用处很大。（专门为了优化算法而准备）

王争老师用的是256字符的数组，我就直接用c++的unordered_map。写的时候想了一下，感觉不对，现在想了下感觉很对（算了算了就用数组把）。

// 把模式字符串保存到哈希表中
int BM::generateBC(std::string pat, int *bc, int bc_size)
{int M = pat.length();// 把所以的字符置为-1for(int i = 0; i<bc_size; i++){bc[i] = -1;}// 往函数中保存pat字母的位数，如果多个重复，以前面的为准，所以需要到者添加for(int i = 0; i<M-1; i++){int ascii = (int)pat.at(i);bc[ascii] = i;}return 0;
}

下面我们接着写只要坏字符的字符串匹配算法：

int BM::bm(std::string pat, std::string str)
{int bc[256];  // 保存pat字符串位置的generateBC(pat, bc, 256);int i = 0;      // i表示主串和模式串对齐的第一个字符while(i < n-m+1){int j =0;for(j=m-1; j>=0; j--){if(str[i+j] != pat[j])  break;  // 如果是坏字符，返回，坏字符下标为j}if(j < 0){return i;       // 如果上面j完成匹配了，j肯定是减到<0,，所以这个条件时匹配成功的返回}// 如果不成功，就要推算往后移动几位了i = i + j - bc[(int)str[i+j]];   // j 其实就是si, 现在重要是xi怎么确定，上面我们已经把下标存储到bc的数组中，// 所以我们只要用这字符去获取就可以了，str[i+j]就是这个坏字符，所以可以这样获取}}

这个比较好写，下面的好后缀就有点难度了。

8.3.2 好后缀规则实现

在讲实现之前，我们先简单的回顾一下，前面好后缀的核心处理规则。

• 在模式串中，查找跟好后缀匹配的另一个子串
• 在好后缀的后缀子串中，查找最长的、能跟模式串前缀子串匹配的后缀子串

在不考虑效率的情况下，这两个操作都可以暴力的匹配查找方法解决，但是，如果想要BM算法的效率很高，这部分就不能太低效。怎么做呢？

这个难度很高啊，先说几个重要概念，之后再分析代码的运行把

1. 如何表示模式串中的不同的后缀子串

   因为后缀子串最后一个位置是固定的，下标为M-1，我们只需要记录长度就可以了，通过长度我们可以确定唯一的后缀子串。

   模式串：c a b c a b

   后缀子串	长度
   b	1
   ab	2
   cab	3
   bcab	4
   abcab	5

2. 引入最关键的变量suffix数组

   suffix数组的下标k,表示后缀子串的长度（就是1中的数），下标对应的数组值存储的是：在模式串中跟好后缀匹配的子串的起始下标

   模式串：c a b c a b

   ​ 0 1 2 3 4 5

   后缀子串	长度	suffix(除去后缀)
   b	1	suffix[1] = 2
   ab	2	suffix[2] = 1
   cab	3	suffix[3] = 0
   bcab	4	suffix[4] = -1
   abcab	5	suffix[5] = -1

   如果模式串中有多个子串匹配后缀子串，我们就选取最大的那个，保证不滑过头。

3. prefix记录，模式串后缀是否匹配模式串的前缀子串

   模式串：c a b c a b

   ​ 0 1 2 3 4 5

   后缀子串	长度	suffix(除去后缀)	prefix
   b	1	suffix[1] = 2	prefix[1] = false
   ab	2	suffix[2] = 1	prefix[2] = false
   cab	3	suffix[3] = 0	prefix[3] = true
   bcab	4	suffix[4] = -1	prefix[4] = false
   abcab	5	suffix[5] = -1	prefix[5] = false

介绍完了，看着还算懂把，就是怎么计算，又是让人头大的事情。

int BM::generateGS(std::string str, int* suffix, boolean* prefix)
{// 先把数组初始化int N = str.length();for(int i = 0; i<N; i++){suffix[i] = -1;prefix[i] = false;}// 开始计算后缀子串长度和是否匹配模式串前缀子串for(int i=0; i<m-1; ++i)       // str[0, i],遍历str字符串，查找后缀{int j = i;           // 从j开始匹配子串int k = 0;          // 公共后缀子串长度，从0开始匹配// 开始匹配while(j >= 0 && str[j] == str[m-1-k])       //是不是就是这里不好理解，说实话我这里也不好理解，看了好几遍才想通了// 我们还是简单来看举例子：// 如果 j = 0  就是比较str[0] == str[m-1]   如果这两个相等，是不是说明收尾两个字符一样，sufffix[1]=1.prefix为ture// 如果 j = 1  str[1] == str[m-1]  如果相等第一个字符和倒数第一个相等，在进入循环// j-- = 0    str[0] == str[m-1-1]  说明前面两个和后面两个字符相等，是不是就suffix[2] = 2// j-- = 0    str[0] != str[m-1-1]  说明两个不相等，是不是就suffix[1] = 1{--j;++k;suffix[k] = j+1;}if(j == -1)  prefix[k] = true;      // j == -1，说明上面完成匹配了，当然相等了。}}

只能说太巧妙了，自己是想不出这种玩法的，接下来，看看根据好后缀规则，计算模式串往后滑动的位数？

假设好后缀的长度是k，我们先拿好后缀，在suffix数组中查找其匹配的子串，会出现下面几种情况：

1. 能匹配到好后缀的情况

   suffix[k] != -1，说明有匹配的子串存在，那我们就将模式串往后移动j-suffix[k]+1（j表示坏字符对应的模式串中的下标，所以需要加1）。

2. 存在不匹配，但是好后缀有匹配模式串前缀的时候

   好后缀的子串b[r, m-1]（其中，r取值从j+2到m-1）的长度k=m-r，prefix[k]= true，表示长度为k的后缀子串，有可能匹配的前缀子串，所以我们可以把模式串后移r位。

3. 都不符合规则

   如果两条规则都没有找到匹配的好后缀及其后缀子串的子串，我们就将整个模式串后移m位。

至此，我们可以看看完整的BM代码了

int BM::bm(std::string pat, std::string str)
{int M = pat.length();int bc[256];  // 保存pat字符串位置的// 坏字符规则generateBC(pat, bc, 256);// 好后缀规则int *suffix = new int[M];bool *prefix = new bool[M];generateGS(str, suffix, prefix);// 开始循环匹配int i = 0;      // i表示主串和模式串对齐的第一个字符while(i < n-m+1){int j =0;for(j=m-1; j>=0; j--){if(str[i+j] != pat[j])  break;  // 如果是坏字符，返回，坏字符下标为j}if(j < 0){return i;       // 如果上面j完成匹配了，j肯定是减到<0,，所以这个条件时匹配成功的返回}// 如果不成功，就要推算往后移动几位了int x = i + j - bc[(int)str[i+j]];   // j 其实就是si, 现在重要是xi怎么确定，上面我们已经把下标存储到bc的数组中，// 所以我们只要用这字符去获取就可以了，str[i+j]就是这个坏字符，所以可以这样获取// 好后缀规则判断int y = 0;if(j < M-1)     // 如果有好后缀的话,这里判断了，不能是m-1,所以必须有一个好后缀{y = moveByGS(j, M, suffix, prefix);}// 移动位数最多的那个i = i + Math.max(x, y);}}int BM::moveByGS(int j, int m, int *suffix, bool *prefix)
{int k = m -1 -j;        //好后缀长度，j是坏字符的下标，所以可以这么算if(suffix[k] != -1) return j - suffix[k] + 1;       // 这是第一种情况for(int r = j+2; r<= m-1; ++r)          // j+2是把完全匹配的跳过，只看后缀{if(prefix[m-r] == true)return r;}return m;               //  如果都没有匹配就直接跳过m
}

有点怀疑人生了。

8.4 性能分析

如果我们处理字符集很大的字符串匹配问题，bc数组对内存消耗就会比较多，如果我们运行环境对内存要求苛刻，可以只使用好后缀规则，不使用坏字符规则。不过单纯使用好后缀规则的BM算法效率就会下降一些。

好像比较复杂，算了，不讲了。