最详细最容易理解的BM算法简介PPT.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Boyer-Moore,算法简介,1,与之前算法的比较,暴力算法 与,KMP,算法 都是基于前缀比较的算法,BM,算法则是基于后缀比较，而且,BM,算法其实上包含两个并行的算法：,坏字符算法,好后缀算法,相同点：,这些算法都是对文本串从左往右分析的,2,朴素的思想,-,坏字符算法,S=,“,FINDINAHAYSTACK,NEEDLE,INA,”,T=,“,NEEDLE,”,FINDI,N,AHAYSTACKNEEDLEINA,N,EEDL,E,3,朴素的思想,-,坏字符算法,S=,“,FINDINAHAYSTACKNEEDLEINA,”,T=,“,NEEDLE,”,FINDI,N,AHAY,S,TACKNEEDLEINA,N,EEDL,E,NEEDL,E,4,朴素的思想,-,坏字符算法,S=,“,FINDINAHAYSTACKNEEDLEINA,”,T=,“,NEEDLE,”,FINDI,N,AHAY,S,TACK,N,E,EDLEINA,N,EEDL,E,NEEDL,E,N,EED,L,E,5,朴素的思想,-,坏字符算法,S=,“,FINDINAHAYSTACKNEEDLEINA,”,T=,“,NEEDLE,”,FINDI,N,AHAY,S,TACK,N,E,EDLEINA,N,EEDL,ENEEDL,E,N,EED,L,E,NEEDLE,6,朴素的思想,-,好后缀算法,CASE 1,S=*,*,BA,BCDE,*,T=A,BCDE,FG,BCDE,7,朴素的思想,-,好后缀算法,CASE 1,S=*,*,BA,BCDE,*,T=A,BCDE,FG,BCDE,T=A,BCDE,FGBCDE,8,朴素的思想,-,好后缀算法,CASE 2,S=*,*,BA,BCDE,*,T=,CDE,CDEG,BCDE,9,朴素的思想,-,好后缀算法,CASE 2,S=*,*,BA,BCDE,*,T=,CDE,CDEG,BCDE,T=,CDE,CDEGBCDE,10,坏字符算法,FINDI,N,AHAY,S,TACK,N,E,EDLEINA,N,EEDL,E,NEEDL,E,N,EED,L,E,NEEDLE,上面的,N,S,N,是坏字符，显然在该算法中存在两种情况：,1.,坏字符不在模式串中,2.,坏,字符在模式串中,11,Case 1,坏字符不在模式串中,*,*,T,LE,*,NEED,LE,NEEDLE,Shift,=,strlen,(,模式串,)-position(,坏,),Shift=6 -2,12,Case 2a,坏字符在模式串中,*,*,N,LE,*,N,EED,LE,NEEDLE,Shift=,最右的坏字符位置,position(,坏,),Shift=,5,-2,13,Case 2b,坏字符在模式串中,*,*,E,LE,*,N,EE,D,LE,14,Case 2b,坏字符在模式串中,*,*,E,LE,*,N,EE,D,LE,NEEDL,E,会有倒退,NE,E,DLE,不能预处理,上面两种设计思想都可行，各有优缺点,15,预处理,-,坏字符,Shift=bmBcSi,-,（,m-1-i,),void preBmBc(char*S,int m,int bmBc),int i;,for(i=0;i ASIZE;+i),/ASIZE=256,bmBci=m;,for(i=0;i=m-1;+i)bmBcSi=m-i-1;,m-i,-1,16,预处理,-,坏字符,void preBmBc(char,*S,int m,int bmBc)int i;,for(i=0;i,ASIZE,;+i),/ASIZE=256,bmBci=m;,for(i=0;i,=m,-1;+i),bmBcSi,=m-i-1;,这,是会有倒退的算法设计，优点在于能够对模式串预处理,17,预处理,-,坏字符,void preBmBc(char,*S,int m,int bmBc)int i;,for(i=0;i,ASIZE,;+i),/ASIZE=256,bmBci=m;,for(i=0;i,=0,；,-i),q=i;,while(q=0&Pq=Pm-1-(i-q),-q;,suffixi=iq;,27,预处理,-,好后缀,void preBmGs(char*x,int m,int bmGs),int i,j,suffXSIZE;,suffixes(x,m,suff);/,对模式串进行预处理,for(i=0;i=0;-i),if(suffi=i+1)/,如果找到一个最大前缀,for(;j m-1-i;+j),if(bmGsj=m),bmGsj=m-1-i;,for(i=0;i=m-2;+i),bmGsm-1-suffi=m-1-i;,28,预处理,-,好后缀,void preBmGs(char*x,int m,int bmGs),int i,j,suffXSIZE;,suffixes(x,m,suff);/,对模式串进行预处理,for(i=0;i=0;-i),if(suffi=i+1)/,如果找到一个最大前缀,for(;j m-1-i;+j),if(bmGsj=m),bmGsj=m-1-i;,for(i=0;i=m-2;+i),bmGsm-1-suffi=m-1-i;,模式串中没有子串匹配上好后缀，但找不到一个最大前缀的情况,29,预处理,-,好后缀,void preBmGs(char*x,int m,int bmGs),int i,j,suffXSIZE;,suffixes(x,m,suff);/,对模式串进行预处理,for(i=0;i=0;-i),if(suffii+1)/,如果找到一个最大前缀,for(;j m-1-i;+j),if(bmGsj=m),bmGsj=m-1-i;,for(i=0;i=m-2;+i),bmGsm-1-suffi=m-1-i;,模式串中没有子串匹配上好后缀，但找不到一个最大前缀的情况,模式串中没有子串匹配上好后缀，但找得到一个最大前缀的情况,30,预处理,-,好后缀,void preBmGs(char*x,int m,int bmGs),int i,j,suffXSIZE;,suffixes(x,m,suff);/,对模式串进行预处理,for(i=0;i=0;-i),if(suffi=i+1)/,如果找到一个最大前缀,for(;j m-1-i;+j),if(bmGsj=m),bmGsj=m-1-i;,for(i=0;i=m-2;+i),bmGsm-1-suffi=m-1-i;,模式串中没有子串匹配上好后缀，但找不到一个最大前缀的情况,模式串中没有子串匹配上好后缀，但找得到一个最大前缀的情况,模式串中有子串匹配上好后缀,31,预处理,-,好后缀,void preBmGs(char*x,int m,int bmGs),int i,j,suffXSIZE;,suffixes(x,m,suff);/,对模式串进行预处理,for(i=0;i=0;-i),if(suffi=i+1)/,如果找到一个最大前缀,for(;j m1-i;+j),if(bmGsj=m),bmGsj=m-1-i;,for(i=0;i=m-2;+i),bmGsm-1-suffi=m-1-i;,O(M),32,算法主体,Int BM_Search(char*S,char*T),j=0,；,while(j=0 -i),if(i 0),match,；,else,j+=max(bmGsi,bmBcTi-,（,m-1-i),；,33,算法主体,Int BM_Search(char*S,char*T),j=0,；,while(j=0 -i),if(i 0),match,；,else,j+=max(bmGsi,bmBcTi-,（,m-1-i),；,最好时,O(strlen(S)/strlen(T),最坏时,O(strlen(S)*strlen(T),34,总结,BM,算法的关键主要在于对于两个数组的预处理。,坏字符串 与 好后缀 都是尽可能的将模式串尽可能地往右移动。,35,