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

《最详细最容易理解的BM算法简介资料讲解.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最详细最容易理解的BM算法简介朴素的思想-坏字符算法S=“FINDINAHAYSTACKNEEDLEINA”T=“NEEDLE”FINDINAHAYSTACKNEEDLEINANEEDLE朴素的思想-坏字符算法S=“FINDINAHAYSTACKNEEDLEINA”T=“NEEDLE”FINDINAHAYSTACKNEEDLEINANEEDLENEEDLE朴素的思想-坏字符算法S=“FINDINAHAYSTACKNEEDLEINA”T=“NEEDLE”FINDINAHAYSTACKNEEDLEINANEEDLENEEDLEN

2、EEDLE朴素的思想-坏字符算法S=“FINDINAHAYSTACKNEEDLEINA”T=“NEEDLE”FINDINAHAYSTACKNEEDLEINANEEDLENEEDLENEEDLENEEDLE朴素的思想-好后缀算法CASE1S=*******BABCDE********T=ABCDEFGBCDE朴素的思想-好后缀算法CASE1S=*******BABCDE********T=ABCDEFGBCDET=ABCDEFGBCDE朴素的思想-好后缀算法CASE2S=*******BABCDE********T=CDECD

3、EGBCDE朴素的思想-好后缀算法CASE2S=*******BABCDE********T=CDECDEGBCDET=CDECDEGBCDE坏字符算法FINDINAHAYSTACKNEEDLEINANEEDLENEEDLENEEDLENEEDLE上面的N,S,N是坏字符，显然在该算法中存在两种情况：1.坏字符不在模式串中2.坏字符在模式串中Case1坏字符不在模式串中*******TLE********NEEDLENEEDLEShift=strlen(模式串)-position(坏)Shift=6-2Case2a坏字符在模

4、式串中*******NLE********NEEDLENEEDLEShift=最右的坏字符位置–position(坏)Shift=5-2Case2b坏字符在模式串中*******ELE********NEEDLECase2b坏字符在模式串中*******ELE********NEEDLENEEDLE会有倒退NEEDLE不能预处理上面两种设计思想都可行，各有优缺点预处理-坏字符Shift=bmBc[S[i]]-（m-1-i)voidpreBmBc(char*S,intm,intbmBc[]){inti;for(i=0;i

5、IZE;++i)//ASIZE=256bmBc[i]=m;for(i=0;i<=m-1;++i)bmBc[S[i]]=m-i-1;}m-i-1预处理-坏字符voidpreBmBc(char*S,intm,intbmBc[]){inti;for(i=0;i

6、ti;for(i=0;i

7、算法中有的是使用了不后退的思路。好后缀算法当好后缀在模式串中重复出现时S=*******BABCDE********T=ABCDEFGBCDE好后缀算法当好后缀在模式串中重复出现时S=*******BABCDE********T=ABCDEFGBCDET=ABCDEFGBCDE好后缀算法模式串中没有子串匹配好后缀S=*******BABCDE********T=CDECDEGBCDE好后缀算法模式串中没有子串匹配好后缀S=*******BABCDE********T=CDECDEGBCDET=CDECDEGBCDE此时需要寻

8、找模式串的一个最长前缀CDE，并让该前缀等于好后缀BCDE的后缀，寻找到该前缀后，让该前缀和好后缀对齐即可。好后缀算法模式串中没有子串匹配上好后缀，并且在模式串中找不到最长前缀，让该前缀等于好后缀的后缀时S=*******BABCDE********T=AACDEFGBCDE好后缀算法模式