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

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

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

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

4、t = 6 - 2,Case 2a,坏字符在模式串中 *NLE* NEEDLE NEEDLE Shift =最右的坏字符位置position(坏) Shift = 5 - 2,Case 2b,坏字符在模式串中 *ELE* NEEDLE,Case 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=

5、256 bmBci = m; for (i = 0; i =m - 1; +i) bmBcSi = m - i - 1; ,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 =m - 1; +i) bmBcSi = m - i - 1; 这是会有倒退的算法设计，优点在于能够对模式串预处理,预处理-坏字符,void preBmBc(char *S, int m, int bmBc) int i; for

6、(i = 0; i ASIZE; +i) /ASIZE=256 bmBci = m; for (i = 0; i =m - 1; +i) bmBcSi = m - i - 1; 这是会有倒退的算法设计，优点在于能够对模式串预处理,O(M),思考题,为什么坏字符算法虽然倒退但是我们还是用这个算法呢？ 解答： 坏字符算法虽然倒退，但是BM算法中好后缀算法是确保不后退的，我们每次移动是取两个算法的最大值。这样一结合就保证了模式串不会倒退。 而坏字符算法虽然后退但是有着能够预处理，代码实现简单，时间复杂度低的特点，所以被广为接受。在后面的SUNDAY 算法等改进算法中有的是使用了不后退的思路。,好后缀

7、算法,当好后缀在模式串中重复出现时 S= *BABCDE* T= ABCDEFGBCDE,好后缀算法,当好后缀在模式串中重复出现时 S= *BABCDE* T= ABCDEFGBCDE T= ABCDEFGBCDE,好后缀算法,模式串中没有子串匹配好后缀 S= *BABCDE* T= CDECDEGBCDE,好后缀算法,模式串中没有子串匹配好后缀 S= *BABCDE* T= CDECDEGBCDE T= CDECDEGBCDE 此时需要寻找模式串的一个最长前缀CDE，并让该前缀等于好后缀BCDE的后缀，寻找到该前缀后，让该前缀和好后缀对齐即可。,好后缀算法,模式串中没有子串匹配上好后缀，并且

8、在模式串中找不到最长前缀，让该前缀等于好后缀的后缀时 S= *BABCDE* T= AACDEFGBCDE,好后缀算法,模式串中没有子串匹配上好后缀，并且在模式串中找不到最长前缀，让该前缀等于好后缀的后缀时 S= *BABCDE* T= AACDEFGBCDE T= AACDEFGBCDE,预处理-好后缀,模式串的预处理 定义一个数组suffix，其中suffixi = s 表示以i为边界，与模式串后缀匹配的最大长度，如下图所示，用公式可以描述：满足Ti-s, i = Tm-s, m的最大长度s。,预处理-好后缀,suffixm-1=m; for (i=m-2；i=0；-i) q=i; whi

9、le(q=0 ,预处理-好后缀,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; ,预处理-好后缀,void preBmGs

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

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

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

13、不到一个最大前缀的情况,模式串中没有子串匹配上好后缀，但找得到一个最大前缀的情况,模式串中有子串匹配上好后缀,预处理-好后缀,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; ,O(M),算法主体,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)； ,算法主体,Int