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 不能預(yù)處理 上面兩種設(shè)計思想都可行，各有優(yōu)缺點,預(yù)處理-壞字符,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,預(yù)處理-壞字符,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; 這是會有倒退的算法設(shè)計，優(yōu)點在于能夠?qū)δＪ酱A(yù)處理,預(yù)處理-壞字符,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; 這是會有倒退的算法設(shè)計，優(yōu)點在于能夠?qū)δＪ酱A(yù)處理,O(M),思考題,為什么壞字符算法雖然倒退但是我們還是用這個算法呢？ 解答： 壞字符算法雖然倒退，但是BM算法中好后綴算法是確保不后退的，我們每次移動是取兩個算法的最大值。這樣一結(jié)合就保證了模式串不會倒退。 而壞字符算法雖然后退但是有著能夠預(yù)處理，代碼實現(xiàn)簡單，時間復(fù)雜度低的特點，所以被廣為接受。在后面的SUNDAY 算法等改進(jìn)算法中有的是使用了不后退的思路。,好后綴

7、算法,當(dāng)好后綴在模式串中重復(fù)出現(xiàn)時 S= *BABCDE* T= ABCDEFGBCDE,好后綴算法,當(dāng)好后綴在模式串中重復(fù)出現(xiàn)時 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,預(yù)處理-好后綴,模式串的預(yù)處理 定義一個數(shù)組suffix，其中suffixi = s 表示以i為邊界，與模式串后綴匹配的最大長度，如下圖所示，用公式可以描述：滿足Ti-s, i = Tm-s, m的最大長度s。,預(yù)處理-好后綴,suffixm-1=m; for (i=m-2；i=0；-i) q=i; whi

9、le(q=0 ,預(yù)處理-好后綴,void preBmGs(char *x, int m, int bmGs) int i, j, suffXSIZE; suffixes(x, m, suff); /對模式串進(jìn)行預(yù)處理 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; ,預(yù)處理-好后綴,void preBmGs

10、(char *x, int m, int bmGs) int i, j, suffXSIZE; suffixes(x, m, suff); /對模式串進(jìn)行預(yù)處理 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; ,模式串中沒有子串匹配上好后綴，但找不到一個最大前綴的情況,預(yù)處理-好后綴,void preBmG

11、s(char *x, int m, int bmGs) int i, j, suffXSIZE; suffixes(x, m, suff); /對模式串進(jìn)行預(yù)處理 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、到一個最大前綴的情況,預(yù)處理-好后綴,void preBmGs(char *x, int m, int bmGs) int i, j, suffXSIZE; suffixes(x, m, suff); /對模式串進(jìn)行預(yù)處理 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、不到一個最大前綴的情況,模式串中沒有子串匹配上好后綴，但找得到一個最大前綴的情況,模式串中有子串匹配上好后綴,預(yù)處理-好后綴,void preBmGs(char *x, int m, int bmGs) int i, j, suffXSIZE; suffixes(x, m, suff); /對模式串進(jìn)行預(yù)處理 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