【字符串匹配】BM(Boyer-Moore)字符串匹配算法详解总结(附C++实现代
码)
BM算法思想的本质上就是在进⾏模式匹配的过程中,当模式串与主串的某个字符不匹配的时候,能够跳过⼀些肯定不会匹配的情况,将模式串往后多滑动⼏位。
BM算法寻是否能多滑动⼏位的原则有两种,分别是坏字符规则和好后缀规则。
坏字符规则:
我们从模式串的末尾往前倒着匹配,当我们发现某个字符⽆法匹配时,我们把这个⽆法匹配的字符叫做坏字符(主串中的字符)。此时记录下坏字符在模式串中的位置si,然后拿坏字符在模式串中查,如果模式串中并不存在这个字符,那么可以将模式串直接向后滑动m位,如果坏字符在模式串中存在,则记录下其位置xi,那么模式串向后移动的位数就是si-xi,(可以在确保si>xi,执⾏减法,不会出现向前移动的情况)。如果坏字符在模式串中多次出现,那我们在计算xi的时候,选择最靠后的那个,这样不会因为让模式串滑动过多,导致本来可能匹配的情况被略过。
好后缀规则:
在我们反向匹配模式串时,遇到不匹配时,记录下当前位置j位坏字符位置。把已经匹配的字符串叫做好后缀,记作{u}。我们拿它在模式串中查,如果到了另⼀个跟{u}相匹配的字串{u*},那么我们就将模式串滑动到字串{u*}与主串{u}对齐的位置。如下图所⽰:
如果在模式串中不到另⼀个等于{u}的⼦串,我们就直接将模式串滑动到主串中{u}的后⾯,因为之前的任何⼀次往后滑动,都没有匹配主串中{u}的情况。但是这种滑动做法有点太过头了,可以看下⾯的例⼦,如果直接滑动到好后缀的后⾯,可能会错过模式串与主串可以匹配的情况。如下图:
当模式串滑动到前缀与主串中{u}的后缀有部分重合的时候,并且重回部分相等的时候,就可能会存在完
全匹配的情况。所以针对这种情况我们不仅要看好后缀在模式串中,是否有另⼀个匹配的字串,我们还要考察好后缀的后缀字串是否存在跟模式串的前缀字串匹配的情况。如下图所⽰:
最后总结如何确定模式串向后滑动的位数,我们可以分别计算好后缀和坏字符往后滑动的位数,然后取两个数中最⼤的。
BM算法性能分析
BM算法的内存消耗:整个算法使⽤了三个额外数组,其中bc数组的⼤⼩和字符集⼤⼩有关,suffix数组和prefix数组的⼤⼩和模式串长度m有关。
如果我们处理字符集很⼤的模式匹配问题,bc数组对内存消耗会⽐较多。好后缀规则和坏字符规则是独⽴的,如果对内存要求苛刻,那么可以只使⽤好后缀规则。不过效率也会下降⼀些。
BM 算法的时间复杂度分析很复杂,原⽂中作者给出了两篇参考⽂章。我也没看,(捂脸)
下⾯给出了BM算法的C++实现
#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
const int size = 256;
字符串长度规则//将模式串字符使⽤hash表⽰
void generateBC(char b[], int m, int bc[]){
//b是模式串, m是模式串的长度, bc是散列表
//bc的下标是字符集的ASCII码,数组值是每个字符在模式串中出现的位置。
for(int i=0; i<size; i++){
bc[i]=-1;
}
for(int i=0; i<m; i++){
int ascii = (int)b[i];
bc[ascii] = i;
}
}
/*
求suffix数组和prefix数组
suffix数组的下标K表⽰后缀字串的长度,数组值对应存储的是,在模式串中跟好后缀{u}相匹配的⼦串{u*}的起始下标值。
prefix数组是布尔型。来记录模式串的后缀字串是否能匹配模式串的前缀⼦串。
*/
void generateGS(char b[], int m, int suffix[], bool prefix[]){
for(int i=0; i<m;i++){
suffix[i] = -1;
prefix[i] = false;
}
for(int i=0; i<m-1; ++i){
int j = i;
int k =0; //公共后缀字串长度
while(j >=0 && b[j] == b[m-1-k]){
//与b[0, m-1]求公共后缀字串
--j;
++k;
suffix[k] = j+1; //j+1表⽰公共后缀字串在b[0,i]中的起始下标
}
if(j == -1) prefix[k] = true;//如果公共后缀字串也是模式串的前缀字串
}
}
//j表⽰坏字符对应的模式串中的字符下标,m是模式串的长度
//计算在好后缀规则下模式串向后移动的个数
int moveByGS(int j, int m, int suffix[], bool prefix[]){
int k= m-1-j; //好后缀的长度
if(suffix[k] != -1) return j - suffix[k] +1;
for(int r = j+2; r<= m-1; ++r){
if(prefix[m-r] == 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=0; //表⽰主串与模式串对齐的第⼀个字符
while(i<=n-m){
int j;
for(j=m-1; j>=0; j--){ //模式串从后往前匹配
if(a[i+j]!= b[j]) break; //坏字符对应的模式串下标是j,即i+j 位置是坏字符的位置si
}
if(j < 0){
return i; //匹配成功,返回主串与模式串第⼀个匹配的字符的位置
}
//这⾥x等同于将模式串往后滑动j-bc[(int)a[i+j]]位
//bc[(int)a[i+j]]表⽰主串中坏字符在模式串中出现的位置xi
int x = i + (j - bc[(int)a[i+j]]);
int y =0;
if(j < m-1){//如果有好后缀的话,计算在此情况下向后移动的位数y
y = moveByGS(j, m, suffix, prefix);
}
i = i + max(x, y); //i更新位可以后移较多的位置
}
return -1;
}
int main(){
char a[] = "aaaabaaba";
char b[] = "aaaa";
int i = BM(a,9,b,2);
printf("%d\n", i);
return 0;
}

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。