c++bm算法

参考资料&＃xff1a;【极客时间.王峥】https://time.geekbang.org/column/article/71525
文中图片均来自极客时间截图。

BM算法思想的本质上就是在进行模式匹配的过程中&＃xff0c;当模式串与主串的某个字符不匹配的时候&＃xff0c;能够跳过一些肯定不会匹配的情况&＃xff0c;将模式串往后多滑动几位。

BM算法寻找是否能多滑动几位的原则有两种&＃xff0c;分别是 坏字符规则 和 好后缀规则。

坏字符规则&＃xff1a;
我们从模式串的末尾往前倒着匹配&＃xff0c;当我们发现某个字符无法匹配时&＃xff0c;我们把这个无法匹配的字符叫做坏字符&＃xff08;主串中的字符&＃xff09;。此时记录下坏字符在模式串中的位置si&＃xff0c;然后拿坏字符在模式串中查找&＃xff0c;如果模式串中并不存在这个字符&＃xff0c;那么可以将模式串直接向后滑动m位&＃xff0c;如果坏字符在模式串中存在&＃xff0c;则记录下其位置xi&＃xff0c;那么模式串向后移动的位数就是si-xi&＃xff0c;&＃xff08;可以在确保si>xi&＃xff0c;执行减法&＃xff0c;不会出现向前移动的情况&＃xff09;。如果坏字符在模式串中多次出现&＃xff0c;那我们在计算xi的时候&＃xff0c;选择最靠后的那个&＃xff0c;这样不会因为让模式串滑动过多&＃xff0c;导致本来可能匹配的情况被略过。

好后缀规则&＃xff1a;
在我们反向匹配模式串时&＃xff0c;遇到不匹配时&＃xff0c;记录下当前位置j位坏字符位置。把已经匹配的字符串叫做好后缀&＃xff0c;记作{u}。我们拿它在模式串中查找&＃xff0c;如果找到了另一个跟{u}相匹配的字串{u*}&＃xff0c; 那么我们就将模式串滑动到字串{u*}与主串{u}对齐的位置。如下图所示&＃xff1a;

如果在模式串中找不到另一个等于{u}的子串&＃xff0c;我们就直接将模式串滑动到主串中{u}的后面&＃xff0c;因为之前的任何一次往后滑动&＃xff0c;都没有匹配主串中{u}的情况。但是这种滑动做法有点太过头了&＃xff0c;可以看下面的例子&＃xff0c;如果直接滑动到好后缀的后面&＃xff0c;可能会错过模式串与主串可以匹配的情况。如下图&＃xff1a;

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

最后总结如何确定模式串向后滑动的位数&＃xff0c;我们可以分别计算好后缀和坏字符往后滑动的位数&＃xff0c;然后取两个数中最大的。

BM算法性能分析
BM算法的内存消耗&＃xff1a;整个算法使用了三个额外数组&＃xff0c;其中bc数组的大小和字符集大小有关&＃xff0c;suffix数组和prefix数组的大小和模式串长度m有关。
如果我们处理字符集很大的模式匹配问题&＃xff0c;bc数组对内存消耗会比较多。好后缀规则和坏字符规则是独立的&＃xff0c;如果对内存要求苛刻&＃xff0c;那么可以只使用好后缀规则。不过效率也会下降一些。
BM 算法的时间复杂度分析很复杂&＃xff0c;原文中作者给出了两篇参考文章。我也没看&＃xff0c;&＃xff08;捂脸&＃xff09;
A new proof of the linearity of the Boyer-Moore string searching algorithm
Tight bounds on the complexity of the Boyer-Moore string matching algorithm

下面给出了BM算法的C&＃43;&＃43;实现

#include
#include
#include
using namespace std;
const int size &＃61; 256;
//将模式串字符使用hash表示
void generateBC(char b[], int m, int bc[]){
//b是模式串&＃xff0c; m是模式串的长度&＃xff0c; bc是散列表
//bc的下标是字符集的ASCII码&＃xff0c;数组值是每个字符在模式串中出现的位置。
for(int i&＃61;0; ibc[i]&＃61;-1;
}
for(int i&＃61;0; iint ascii &＃61; (int)b[i];
bc[ascii] &＃61; i;
}
}
/*
求suffix数组和prefix数组
suffix数组的下标K表示后缀字串的长度&＃xff0c;数组值对应存储的是&＃xff0c;在模式串中跟好后缀{u}相匹配的子串{u*}
的起始下标值。
prefix数组是布尔型。来记录模式串的后缀字串是否能匹配模式串的前缀子串。*/
void generateGS(char b[], int m, int suffix[], bool prefix[]){
for(int i&＃61;0; isuffix[i] &＃61; -1;
prefix[i] &＃61; false;
}
for(int i&＃61;0; iint j &＃61; i;
int k &＃61;0; //公共后缀字串长度
while(j >&＃61;0 && b[j] &＃61;&＃61; b[m-1-k]){
//与b[0, m-1]求公共后缀字串
--j;
&＃43;&＃43;k;
suffix[k] &＃61; j&＃43;1; //j&＃43;1表示公共后缀字串在b[0,i]中的起始下标
}
if(j &＃61;&＃61; -1) prefix[k] &＃61; true;//如果公共后缀字串也是模式串的前缀字串}
}//j表示坏字符对应的模式串中的字符下标&＃xff0c;m是模式串的长度
//计算在好后缀规则下模式串向后移动的个数
int moveByGS(int j, int m, int suffix[], bool prefix[]){
int k&＃61; m-1-j; //好后缀的长度
if(suffix[k] !&＃61; -1) return j - suffix[k] &＃43;1;
for(int r &＃61; j&＃43;2; r<&＃61; m-1; &＃43;&＃43;r){
if(prefix[m-r] &＃61;&＃61; true){
return r;
}
}
return m;
}//BM算法
int BM(char a[], int n, char b[], int m){
int suffix[m];
bool prefix[m];int bc[size];//bc记录模式串中每个字符最后出现的位置generateBC(b,m,bc); //构建字符串hash表
generateGS(b,m, suffix,prefix); //计算好后缀和好前缀数组int i&＃61;0; //表示主串与模式串对齐的第一个字符
while(i<&＃61;n-m){
int j;
for(j&＃61;m-1; j>&＃61;0; j--){ //模式串从后往前匹配
if(a[i&＃43;j]!&＃61; b[j]) break; //坏字符对应的模式串下标是j,即i&＃43;j 位置是坏字符的位置si        
}
if(j <0){
return i; //匹配成功&＃xff0c;返回主串与模式串第一个匹配的字符的位置
}
//这里x等同于将模式串往后滑动j-bc[(int)a[i&＃43;j]]位
//bc[(int)a[i&＃43;j]]表示主串中坏字符在模式串中出现的位置xi
int x &＃61; i &＃43; (j - bc[(int)a[i&＃43;j]]); int y &＃61;0;
if(j y &＃61; moveByGS(j, m, suffix, prefix);
}
i &＃61; i &＃43; max(x, y); //i更新位可以后移较多的位置}
return -1;
}int main(){
char a[] &＃61; "aaaabaaba";
char b[] &＃61; "aaaa";
int i &＃61; BM(a,9,b,2);
printf("%d\n", i);
return 0;
}