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

《最详细最容易理解的BM算法简介.ppt》由会员分享，可在线阅读，更多相关《最详细最容易理解的BM算法简介.ppt（35页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、Boyer-Moore算法简介与之前算法的比较暴力算法 与 KMP算法 都是基于前缀比较的算法BM算法则是基于后缀比较，而且BM算法其实上包含两个并行的算法：坏字符算法好后缀算法相同点：这些算法都是对文本串从左往右分析的 朴素的思想-坏字符算法S=“FINDINAHAYSTACKNEEDLEINA”T=“NEEDLE”FINDINAHAYSTACKNEEDLEINA NEEDLE 朴素的思想-坏字符算法S=“FINDINAHAYSTACKNEEDLEINA”T=“NEEDLE”FINDINAHAYSTACKNEEDLEINA NEEDLE NEEDLE 朴素的思想-坏字符算法S=“FINDIN

2、AHAYSTACKNEEDLEINA”T=“NEEDLE”FINDINAHAYSTACKNEEDLEINA NEEDLE NEEDLE NEEDLE 朴素的思想-坏字符算法S=“FINDINAHAYSTACKNEEDLEINA”T=“NEEDLE”FINDINAHAYSTACKNEEDLEINA NEEDLE NEEDLE NEEDLE NEEDLE 朴素的思想-好后缀算法CASE 1S=*BABCDE*T=ABCDEFGBCDE 朴素的思想-好后缀算法CASE 1S=*BABCDE*T=ABCDEFGBCDET=ABCDEFGBCDE 朴素的思想-好后缀算法CASE 2S=*BABCDE*T

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

4、最右的坏字符位置position(坏)Shift=5 -2Case 2b坏字符在模式串中坏字符在模式串中*ELE*NEEDLECase 2b坏字符在模式串中坏字符在模式串中*ELE*NEEDLE NEEDLE 会有倒退 NEEDLE 不能预处理上面两种设计思想都可行，各有优缺点预处理-坏字符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预处理-坏字符void preBmBc(

5、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;这是会有倒退的算法设计，优点在于能够对模式串预处理预处理-坏字符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=i-q;预处理-好后缀void preBmGs(char*x,int m,int

6、 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;预处理-好后缀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)/如果找到一个最大前缀

7、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;模式串中没有子串匹配上好后缀，但找模式串中没有子串匹配上好后缀，但找不到一个最大前缀的情况不到一个最大前缀的情况预处理-好后缀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

8、;for(i=0;i=m-2;+i)bmGsm-1-suffi=m-1-i;模式串中没有子串匹配上好后缀，但找模式串中没有子串匹配上好后缀，但找不到一个最大前缀的情况不到一个最大前缀的情况模式串中没有子串匹配上好后缀，但找模式串中没有子串匹配上好后缀，但找得到一个最大前缀的情况得到一个最大前缀的情况预处理-好后缀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(b

9、mGsj=m)bmGsj=m-1-i;for(i=0;i=m-2;+i)bmGsm-1-suffi=m-1-i;模式串中没有子串匹配上好后缀，但找模式串中没有子串匹配上好后缀，但找不到一个最大前缀的情况不到一个最大前缀的情况模式串中没有子串匹配上好后缀，但找模式串中没有子串匹配上好后缀，但找得到一个最大前缀的情况得到一个最大前缀的情况模式串中有子串匹配上好后缀模式串中有子串匹配上好后缀预处理-好后缀void preBmGs(char*x,int m,int bmGs)int i,j,suffXSIZE;suffixes(x,m,suff);/对模式串进行预处理 for(i=0;i=0;-i)i

10、f(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;O(M)算法主体Int BM_Search(char*S,char*T)j=0；while(j=0&Ti=Si+j;-i)if(i 0)match；else j+=max(bmGsi,bmBcTi-（m-1-i)；算法主体Int BM_Search(char*S,char*T)j=0；while(j=0&Ti=Si+j;-i)if(i 0)match；else j+=max(bmGsi,bmBcTi-（m-1-i)；最好时最好时最好时最好时O(strlen(S)/strlen(T)O(strlen(S)/strlen(T)最坏时最坏时最坏时最坏时O(strlen(S)*strlen(T)O(strlen(S)*strlen(T)总结BM算法的关键主要在于对于两个数组的预处理。坏字符串 与 好后缀 都是尽可能的将模式串尽可能地往右移动。