最详细最容易理解的BM算法简介PPT课件

.,1,Boyer-Moore算法简介,.,2,与之前算法的比较,暴力算法与KMP算法都是基于前缀比较的算法BM算法则是基于后缀比较，而且BM算法其实上包含两个并行的算法：坏字符算法好后缀算法相同点：这些算法都是对文本串从左往右分析的,.,3,朴素的思想-坏字符算法,S=“FINDINAHAYSTACKNEEDLEINA”T=“NEEDLE”FINDINAHAYSTACKNEEDLEINANEEDLE,.,4,朴素的思想-坏字符算法,S=“FINDINAHAYSTACKNEEDLEINA”T=“NEEDLE”FINDINAHAYSTACKNEEDLEINANEEDLENEEDLE,.,5,朴素的思想-坏字符算法,S=“FINDINAHAYSTACKNEEDLEINA”T=“NEEDLE”FINDINAHAYSTACKNEEDLEINANEEDLENEEDLENEEDLE,.,6,朴素的思想-坏字符算法,S=“FINDINAHAYSTACKNEEDLEINA”T=“NEEDLE”FINDINAHAYSTACKNEEDLEINANEEDLENEEDLENEEDLENEEDLE,.,7,朴素的思想-好后缀算法,CASE1S=*BABCDE*T=ABCDEFGBCDE,.,8,朴素的思想-好后缀算法,CASE1S=*BABCDE*T=ABCDEFGBCDET=ABCDEFGBCDE,.,9,朴素的思想-好后缀算法,CASE2S=*BABCDE*T=CDECDEGBCDE,.,10,朴素的思想-好后缀算法,CASE2S=*BABCDE*T=CDECDEGBCDET=CDECDEGBCDE,.,11,坏字符算法,FINDINAHAYSTACKNEEDLEINANEEDLENEEDLENEEDLENEEDLE上面的N,S,N是坏字符，显然在该算法中存在两种情况：1.坏字符不在模式串中2.坏字符在模式串中,.,12,Case1,坏字符不在模式串中*TLE*NEEDLENEEDLEShift=strlen(模式串)-position(坏)Shift=6-2,.,13,Case2a,坏字符在模式串中*NLE*NEEDLENEEDLEShift=最右的坏字符位置position(坏)Shift=5-2,.,14,Case2b,坏字符在模式串中*ELE*NEEDLE,.,15,Case2b,坏字符在模式串中*ELE*NEEDLENEEDLE会有倒退NEEDLE不能预处理上面两种设计思想都可行，各有优缺点,.,16,预处理-坏字符,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,.,17,预处理-坏字符,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;这是会有倒退的算法设计，优点在于能够对模式串预处理,.,18,预处理-坏字符,voidpreBmBc(char*S,intm,intbmBc)inti;for(i=0;i=0,.,28,预处理-好后缀,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;,.,29,预处理-好后缀,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;,模式串中没有子串匹配上好后缀，但找不到一个最大前缀的情况,.,30,预处理-好后缀,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;,模式串中没有子串匹配上好后缀，但找不到一个最大前缀的情况,模式串中没有子串匹配上好后缀，但找得到一个最大前缀的情况,.,31,预处理-好后缀,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;,模式串中没有子串匹配上好后缀，但找不到一个最大前缀的情况,模式串中没有子串匹配上好后缀，但找得到一个最大前缀的情况,模式串中有子串匹配上好后缀,.,32,预处理-好后缀,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),.,33,算法主体,IntBM_Search(char*S,char*T)j=0；while(j=0-i)if(i0)match；elsej+=max(bmGsi,bmBcTi-（m-1-i)；,.,34,算法主体,IntBM_Search(char*S,char*T)j=0；while(j=0-i)if(i0)m