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

Boyer-Moore算法简介,与之前算法的比较,暴力算法与KMP算法都是基于前缀比较的算法BM算法则是基于后缀比较，而且BM算法其实上包含两个并行的算法：坏字符算法好后缀算法相同点：这些算法都是对文本串从左往右分析的,朴素的思想-坏字符算法,S=“FINDINAHAYSTACKNEEDLEINA”T=“NEEDLE”FINDINAHAYSTACKNEEDLEINANEEDLE,朴素的思想-坏字符算法,S=“FINDINAHAYSTACKNEEDLEINA”T=“NEEDLE”FINDINAHAYSTACKNEEDLEINANEEDLENEEDLE,朴素的思想-坏字符算法,S=“FINDINAHAYSTACKNEEDLEINA”T=“NEEDLE”FINDINAHAYSTACKNEEDLEINANEEDLENEEDLENEEDLE,朴素的思想-坏字符算法,S=“FINDINAHAYSTACKNEEDLEINA”T=“NEEDLE”FINDINAHAYSTACKNEEDLEINANEEDLENEEDLENEEDLENEEDLE,朴素的思想-好后缀算法,CASE1S=*BABCDE*T=ABCDEFGBCDE,朴素的思想-好后缀算法,CASE1S=*BABCDE*T=ABCDEFGBCDET=ABCDEFGBCDE,朴素的思想-好后缀算法,CASE2S=*BABCDE*T=CDECDEGBCDE,朴素的思想-好后缀算法,CASE2S=*BABCDE*T=CDECDEGBCDET=CDECDEGBCDE,坏字符算法,FINDINAHAYSTACKNEEDLEINANEEDLENEEDLENEEDLENEEDLE上面的N,S,N是坏字符，显然在该算法中存在两种情况：1.坏字符不在模式串中2.坏字符在模式串中,Case1,坏字符不在模式串中*TLE*NEEDLENEEDLEShift=strlen(模式串)-position(坏)Shift=6-2,Case2a,坏字符在模式串中*NLE*NEEDLENEEDLEShift=最右的坏字符位置position(坏)Shift=5-2,Case2b,坏字符在模式串中*ELE*NEEDLE,Case2b,坏字符在模式串中*ELE*NEEDLENEEDLE会有倒退NEEDLE不能预处理上面两种设计思想都可行，各有优缺点,预处理-坏字符,Shift=bmBcSi-（m-1-i)voidpreBmBc(char*S,intm,intbmBc)inti;for(i=0;iASIZE;+i)/ASIZE=256bmBci=m;for(i=0;i=m-1;+i)bmBcSi=m-i-1;,m-i,-1,预处理-坏字符,voidpreBmBc(char*S,intm,intbmBc)inti;for(i=0;iASIZE;+i)/ASIZE=256bmBci=m;for(i=0;i=m-1;+i)bmBcSi=m-i-1;这是会有倒退的算法设计，优点在于能够对模式串预处理,预处理-坏字符,voidpreBmBc(char*S,intm,intbmBc)inti;for(i=0;i=0,预处理-好后缀,voidpreBmGs(char*x,intm,intbmGs)inti,j,suffXSIZE;suffixes(x,m,suff);/对模式串进行预处理for(i=0;i=0;-i)if(suffi=i+1)/如果找到一个最大前缀for(;jm-1-i;+j)if(bmGsj=m)bmGsj=m-1-i;for(i=0;i=m-2;+i)bmGsm-1-suffi=m-1-i;,预处理-好后缀,voidpreBmGs(char*x,intm,intbmGs)inti,j,suffXSIZE;suffixes(x,m,suff);/对模式串进行预处理for(i=0;i=0;-i)if(suffi=i+1)/如果找到一个最大前缀for(;jm-1-i;+j)if(bmGsj=m)bmGsj=m-1-i;for(i=0;i=m-2;+i)bmGsm-1-suffi=m-1-i;,模式串中没有子串匹配上好后缀，但找不到一个最大前缀的情况,预处理-好后缀,voidpreBmGs(char*x,intm,intbmGs)inti,j,suffXSIZE;suffixes(x,m,suff);/对模式串进行预处理for(i=0;i=0;-i)if(suffi=i+1)/如果找到一个最大前缀for(;jm-1-i;+j)if(bmGsj=m)bmGsj=m-1-i;for(i=0;i=m-2;+i)bmGsm-1-suffi=m-1-i;,模式串中没有子串匹配上好后缀，但找不到一个最大前缀的情况,模式串中没有子串匹配上好后缀，但找得到一个最大前缀的情况,预处理-好后缀,voidpreBmGs(char*x,intm,intbmGs)inti,j,suffXSIZE;suffixes(x,m,suff);/对模式串进行预处理for(i=0;i=0;-i)if(suffi=i+1)/如果找到一个最大前缀for(;jm-1-i;+j)if(bmGsj=m)bmGsj=m-1-i;for(i=0;i=m-2;+i)bmGsm-1-suffi=m-1-i;,模式串中没有子串匹配上好后缀，但找不到一个最大前缀的情况,模式串中没有子串匹配上好后缀，但找得到一个最大前缀的情况,模式串中有子串匹配上好后缀,预处理-好后缀,voidpreBmGs(char*x,intm,intbmGs)inti,j,suffXSIZE;suffixes(x,m,suff);/对模式串进行预处理for(i=0;i=0;-i)if(suffi=i+1)/如果找到一个最大前缀for(;jm-1-i;+j)if(bmGsj=m)bmGsj=m-1-i;for(i=0;i=m-2;+i)bmGsm-1-suffi=m-1-i;,O(M),算法主体,IntBM_Search(char*S,char*T)j=0；while(j=0-i)if(i0)match；elsej+=max(bmGsi,bmBcTi-（m-1-i)；,算法主体,IntBM_Search(char*S,char*T)j=0；while(j=0-i)if(i0)ma