BM algorithm

本文主要是介绍BM algorithm，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

//BM algorithm/*
1: bmbc[p[i]]:p中最右边出现的p[i]字符到p最后一个字符的步长（plen-1-i），但不是坏字符时需要主串移动的步长
2: suffix[i]:p[i]往前推（包括p[i]），与p[len-1]往前推（包括p[len-1]），的最大匹配长度（匹配字符个数）
3: bmgs[i]:p中能够最大匹配p[i+1]到p[len-1]字符的步长，其是好后缀时主串需要移动的步长。分三种情况，p中有完全匹配的，p的开始和结束部分匹配的，完全不匹配的！
*/#include <iostream.h>
#include <string.h>#define CHARMAX  128void init_BMBC(int* bmbc, char* p, int p_len);
void getSuffix(char* p, int* suffix, int p_len);
void init_BMGS(int* bmgs, char* p, int p_len);
int  BM_Search(char* t,char* p);
void show(char* intro, int* out, int len, char* p);void init_BMBC(int* bmbc, char* p, int p_len)
{for(int i=0; i<CHARMAX; i++)bmbc[i]=p_len;for(i=0; i<p_len; i++){bmbc[p[i]]=p_len-i-1;//bmbc[p[i]]:p[i]到p最后的距离}show("bmbc",bmbc,p_len,p);
}void getSuffix(char* p, int* suffix, int p_len)
{suffix[p_len-1]=0;for(int i=p_len-2; i>=0; i--){int m=p_len-1;//m为p的最后下标int n=i;while(n>=0 && p[n]==p[m]){n--;m--;}suffix[i]=i-n;}show("suffix",suffix,p_len,NULL);
}void init_BMGS(int* bmgs, char* p, int p_len)
{int* suffix=new int[p_len];getSuffix(p,suffix,p_len);//to do...bmgs[p_len-1]=0;for(int i=p_len-2; i>=0; i--){int goodSuffixlen=p_len-1-i;bool bmgsFlag=false;for(int j=p_len-2; j>=p_len-1-i; j--){if(goodSuffixlen<=suffix[j])//注意是小于等于，而不是等于，因为小于时，suffix包含了好后缀{bmgs[i]=p_len-1-j;bmgsFlag=true;break;}}if(!bmgsFlag){for(int j=p_len-2-i; j>=0; j--){if(suffix[j]==j+1){bmgs[i]=p_len-1-j;bmgsFlag=true;break;}}}if(!bmgsFlag){bmgs[i]=p_len;}}show("bmgs",bmgs,p_len,NULL);delete suffix;}int BM_Search(char* t,char* p)
{int t_len=strlen(t);int p_len=strlen(p);int bmbc[CHARMAX];int* bmgs=new int[p_len];init_BMBC(bmbc,p,p_len);init_BMGS(bmgs,p,p_len);int k=p_len-1;//k：其为主串的开始匹配位置，每次移动都是移动的kwhile(k<t_len){int i=k;int j=p_len-1;while(j>=0 && t[i]==p[j]){i--;//主串中开始比较的位置j--;//模式串中开始比较的位置}if(j<0){delete bmgs;return k-p_len+1;}else{int step=bmgs[j]>=(bmbc[t[i]]-p_len+1+j) ? bmgs[j] : (bmbc[t[i]]-p_len+1+j);k+=step;}}delete bmgs;return -1;
}void main()
{char* t="abcdefegadfefdsfeabcgfabcabcabcffabcabcaafde";char* p="abcffabcabc";cout<<"t:    "<<t<<"\n"<<"p:    :"<<p<<"\n\n";cout<<"\nmatch position:  "<<BM_Search(t,p)<<endl;}void show(char* intro, int* out, int len, char* p)
{	cout<<intro<<":   ";if(!p)for(int i=0; i<len; i++)cout<<out[i]<<" ";elsefor(int i=0; i<len; i++)cout<<out[p[i]]<<" ";cout<<endl;
}

这篇关于BM algorithm的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---