BM算法实验报告

一、实验内容Boyer-Moore算法的实现（同时已实现KMP/暴力匹配算法，用于实验数据比较）二、实验环境操作系统：PC/Win7编译环境:GCC4.3/Dev-Cpp三、实验原理利用BM算法设定的好后缀/坏字符规则加速匹配，其中求好后缀时需要用到字符串算法z-box，整个算法期望时间复杂度为O(|T|/|P|),最坏时间复杂度为O(|T|*|P|),空间复杂度为O(|P|+|T|)。KMP算法时间复杂度为O(|P|+|T|)，空间复杂度为O(|P|+|T|)。暴力算法时间复杂度为O(|P|*|T|)，空间复杂度为O(|P|+|T|)。四、代码设计#includecstring#includecstdio#includealgorithm#includeiostreamusingnamespacestd;#definemaxlen1100000#definemax(a,b)(a)(b)?(a):(b)intbad[18];//坏字符移动表intL[maxlen]/*最近后缀*/,l[maxlen]/*最长前缀*/;intzbox[maxlen];charP[maxlen],T[maxlen];//模式串，文本串intplen,tlen;//模式串长度，文本串长度voidBadChar(charP[]){//坏字符规则处理intlen=plen;for(inti=0;i(18);++i){bad[i]=len;}for(inti=0;ilen-1;++i){bad[P[i]]=len-1-i;}bad[P[len-1]]=1;}voidGet_Zbox(charP[]){intl,r;l=r=-1,zbox[0]=0;intlen=plen;reverse(P,P+len);for(inti=1;ilen;++i){if(ir){intj=0,k=i;while(klen&&P[j]==P[k]){j++;k++;}if(ki){l=i,r=k-1;}zbox[i]=k-i;}else{if(zbox[i-l]r-i+1)zbox[i]=zbox[i-l];else{zbox[i]=r-i+1;intj=r-i+1,k=r+1;while(klen&&P[j]==P[k]){j++;k++;zbox[i]++;}l=i,r=k-1;}}}reverse(P,P+len);}voidGoodSuff(charP[]){//好后缀规则处理Get_Zbox(P);intlen=plen;memset(L,-1,sizeof(L));for(inti=0;ilen-1;++i){L[len-zbox[len-i-1]]=i;}l[len]=0;intret=-1;for(inti=len-1;i=0;--i){if(zbox[i]==len-i)ret=max(ret,len-i-1);l[i]=ret;}}intJump(intBad,inted,intn){if(L[ed]=0)returnmax(Bad,n-L[ed]-1);if(l[ed]=0)returnmax(Bad,n-l[ed]-1);returnBad;}intBM(charP[],charT[]){BadChar(P);GoodSuff(P);intn=plen;intm=tlen;intk=n-1;while(km){inti=n-1,h=k;while(i=0&&P[i]==T[h]){i--;h--;}if(i0){//若匹配成功则返回k+=n-l[1]-1;returnh+1;}elsek+=Jump(bad[T[h]],i,n);//匹配失败，根据两个规则跳转}return-1;}intnext[maxlen];voidgetnext(charp[]){intlen=plen;next[1]=0;intq;intk=0;for(q=2;q=len;q++){while(k0&&p[k]!=p[q-1])k=next[k];if(p[k]==p[q-1])k++;next[q]=k;}}intKMP(charp[],chart[]){intans=0;inti;intn=tlen;intm=plen;getnext(p);intq=0;for(i=0;in;i++){while(q0&&p[q]!=t[i])q=next[q];if(p[q]==t[i])q++;if(q==m){returni-m+1;ans++;q=next[q];}}return-1;}intfind(charP[],charT[]){intn=tlen;intm=plen;intj;for(inti=0;in;++i){if(i+mn)break;for(j=0;jm;++j){if(P[j]==T[i+j])continue;elsebreak;}if(j==m)returni;}return-1;}intmain(){//freopen(input.txt,r,stdin);while(true){system(cls);printf(请输入模式串:);gets(P);printf(请输入文本串:);gets(T);plen=strlen(P);tlen=strlen(T);intst=clock();intind=BM(P,T);printf(Boyer-Moore:Thefirstmatchedindex:%d,itcosts%dms\n,ind,clock()-st);st=clock();ind=KMP(P,T);printf(KMP:Thefirstmatchedindex:%d,itcosts%dms\n,ind,clock()-st);st=clock();ind=find(P,T);printf(Brute-Force:Thefirstmatchedindex:%d,itcosts%dms\n,ind,clock()-st);printf(是否继续匹配(Y/y)?);charch=getchar();if(ch!='Y'&&ch!='y')break;getchar();}return0;}五、实验结果与分析运行环境为CPU:intel4核2.4GHz内存:2G从表格数据可知随机数据下，三个算法运行时间很接近，当数据规模达到100,1000时所使用的时间基本符合三个算法的期望复杂度。最坏数据下，当数据规模较小(10000)时三个算法的运行时间差不多，在100,000的数据规模下时,KMP处理最坏数据开始有绝对的时间优势。而其他两个算法也满足其最坏情况为O(|P|*|T|)的本质。总结编写这个算法实验时，最开始只是想学习BM这个算法，后来觉得我们对算法的分析都是基于理论的，从来没有用数据验证过，所以有了写其他算法进行比较的想法。最开始实现BM时，由于课本介绍不全，对线性处理好后缀无法解决，后来通过学习其他的书籍资料①才得以解决这个问题，该代码已通过随机大量数据及人造数据验证正确性。这次的实验也让我对各种字符串算法的真正运行时间有了进一步的认识，虽然BM的期望复杂度是亚线性的，但其在面对中小数据规模时却并无真正优势，而其正确性也并不如暴力算法一样容易保证。这是BM的短处，应该也是众多工程代码仍然选用暴力算法的原因。对于其他的亚线性算法（比如Sunday算法），我由于时间问题，没有实现，无法做出比较。附：参考书籍：①《算法艺术与信息学竞赛学习指导》②《算法导论（第二版）》