http://blog.csdn.net/sealyao/article/details/4568167

1,、概述

在用于查找子字符串的算法當中,，BM（Boyer-Moore）算法是目前相當有效又容易理解的一種,，一般情況下,，比KMP算法快3-5倍。

BM算法在移動模式串的時候是從左到右,，而進行比較的時候是從右到左的,。

常規(guī)的匹配算法移動模式串的時候是從左到右，而進行比較的時候也是是從左到右的,，基本框架是：

而BM算法在移動模式串的時候是從左到右，而進行比較的時候是從右到左的,，基本框架是：

顯然BM算法并不是上面那個樣子,，BM算法的精華就在于++j

2、BM算法思想

BM算法實際上包含兩個并行的算法,，壞字符算法和好后綴算法,。這兩種算法的目的就是讓模式串每次向右移動盡可能大的距離（j+=x,，x盡可能的大）,。

幾個定義：

例主串和模式串如下：

主串  :  mahtavaatalomaisema omalomailuun

模式串: maisemaomaloma

好后綴：模式串中的aloma為“好后綴”。

壞字符：主串中的“t”為壞字符,。

好后綴算法

如果程序匹配了一個好后綴, 并且在模式中還有另外一個相同的后綴, 那

把下一個后綴移動到當前后綴位置,。好后綴算法有兩種情況：

Case1：模式串中有子串和好后綴安全匹配,，則將最靠右的那個子串移動到好后綴的位置。繼續(xù)進行匹配,。

Case2：如果不存在和好后綴完全匹配的子串,，則在好后綴中找到具有如下特征的最長子串,使得P[m-s…m]=P[0…s]。說不清楚的看圖,。

壞字符算法

當出現(xiàn)一個壞字符時, BM算法向右移動模式串, 讓模式串中最靠右的對應(yīng)字符與壞字符相對,，然后繼續(xù)匹配。壞字符算法也有兩種情況,。

Case1：模式串中有對應(yīng)的壞字符時,，見圖。

Case2：模式串中不存在壞字符,。見圖,。

移動規(guī)則

BM算法的移動規(guī)則是：

將概述中的++j，換成j+=MAX（shift（好后綴）,，shift（壞字符））,，即

BM算法是每次向右移動模式串的距離是，按照好后綴算法和壞字符算法計算得到的最大值,。

shift（好后綴）和shift（壞字符）通過模式串的預(yù)處理數(shù)組的簡單計算得到,。好后綴算法的預(yù)處理數(shù)組是bmGs[]，壞字符算法的預(yù)處理數(shù)組是BmBc[],。

3,、代碼分析

定義

BM算法子串比較失配時，按壞字符算法計算模式串需要向右移動的距離,，要借助BmBc數(shù)組,。

注意BmBc數(shù)組的下標是字符，而不是數(shù)字,。

BmBc數(shù)組的定義,，分兩種情況。

1,、 字符在模式串中有出現(xiàn),。如下圖，BmBc[‘k’]表示字符k在模式串中最后一次出現(xiàn)的位置,，距離模式串串尾的長度,。

2、 字符在模式串中沒有出現(xiàn)：,，如模式串中沒有字符p,，則BmBc[‘p’] = strlen(模式串)。

BM算法子串比較失配時，按好后綴算法計算模式串需要向右移動的距離,，要借助BmGs數(shù)組,。

BmGs數(shù)組的下標是數(shù)字，表示字符在模式串中位置,。

BmGs數(shù)組的定義,，分三種情況。

1,、 對應(yīng)好后綴算法case1：如下圖：i是好后綴之前的那個位置,。

2、 對應(yīng)好后綴算法case2：如下圖所示：

3,、 當都不匹配時,，BmGs[i] = strlen（模式串）

在計算BmGc數(shù)組時，為提高效率,，先計算輔助數(shù)組Suff,。

Suff數(shù)組的定義：suff[i] = 以i為邊界, 與模式串后綴匹配的最大長度，即P[i-s...i]=P[m-s…m]如下圖：

舉例如下：

分析

用Suff[]計算BmGs的方法,。

1） BmGs[0…m-1] = m,；（第三種情況）

2） 計算第二種情況下的BmGs[]值：

for（i=0；i

if（-1==i || Suff[i] == i+1）

for（,；j < m-1-i,；++j）

if（suff[j] == m）

BmGs[j] = m-1-i；

3） 計算第三種情況下BmGs[]值,，可以覆蓋前兩種情況下的BmGs[]值：

for（i=0,；i

BmGs[m-1-suff[i]] = m-1-i；

如下圖所示：

Suff[]數(shù)組的計算方法,。

常規(guī)的方法：如下,，很裸很暴力。

Suff[m-1]=m,；

for（i=m-2,；i>=0；--i）{

q=i,；

while（q>=0&&P[q]==P[m-1-i+q]）

--q,；

Suff[i]=i-q；

}

有聰明人想出一種方法,，對常規(guī)方法進行改進,。基本的掃描都是從右向左,。改進的地方就是利用了已經(jīng)計算得到的suff[]值,，計算現(xiàn)在正在計算的suff[]值,。

如下圖所示：

i是當前正準備計算的suff[]值得那個位置。

f是上一個成功進行匹配的起始位置（不是每個位置都能進行成功匹配的,，  實際上能夠進行成功匹配的位置并不多）。

q是上一次進行成功匹配的失配位置,。

如果i在q和f之間,，那么一定有P[i]=P[m-1-f+i]；并且如果suff[m-1-f+i]=i-q, suff[i]和suff[m-1-f+i]就沒有直接關(guān)系了,。

代碼

[cpp] view plain copy

1. void preBmBc(char *x, int m, int bmBc[]) {  
2.   
3.    int i;  
4.   
5.    for (i = 0; i < ASIZE; ++i)  
6.   
7.       bmBc[i] = m;  
8.   
9.    for (i = 0; i < m - 1; ++i)  
10.   
11.       bmBc[x[i]] = m - i - 1;  
12.   
13. }  
14.   
15. void suffixes(char *x, int m, int *suff) {  
16.   
17.    int f, g, i;  
18.   
19.   f = 0,；  
20.   
21.    suff[m - 1] = m;  
22.   
23.    g = m - 1;  
24.   
25.    for (i = m - 2; i >= 0; --i) {  
26.   
27.       if (i > g && suff[i + m - 1 - f] < i - g)  
28.   
29.          suff[i] = suff[i + m - 1 - f];  
30.   
31.       else {  
32.   
33.          if (i < g)  
34.   
35.             g = i;  
36.   
37.          f = i;  
38.   
39.          while (g >= 0 && x[g] == x[g + m - 1 - f])  
40.   
41.             --g;  
42.   
43.          suff[i] = f - g;  
44.   
45.       }  
46.   
47.    }  
48.   
49. }  
50.   
51. void preBmGs(char *x, int m, int bmGs[]) {  
52.   
53.    int i, j, suff[XSIZE];  
54.   
55.    suffixes(x, m, suff);  
56.   
57.    for (i = 0; i < m; ++i)  
58.   
59.       bmGs[i] = m;  
60.   
61.    j = 0;  
62.   
63.    for (i = m - 1; i >= 0; --i)  
64.   
65.       if (suff[i] == i + 1)  
66.   
67.          for (; j < m - 1 - i; ++j)  
68.   
69.             if (bmGs[j] == m)  
70.   
71.                bmGs[j] = m - 1 - i;  
72.   
73.    for (i = 0; i <= m - 2; ++i)  
74.   
75.       bmGs[m - 1 - suff[i]] = m - 1 - i;  
76.   
77. }  
78.   
79. void BM(char *x, int m, char *y, int n) {  
80.   
81.    int i, j, bmGs[XSIZE], bmBc[ASIZE];  
82.   
83.    /* Preprocessing */  
84.   
85.    preBmGs(x, m, bmGs);  
86.   
87.    preBmBc(x, m, bmBc);  
88.   
89.    /* Searching */  
90.   
91.    j = 0;  
92.   
93.    while (j <= n - m) {  
94.   
95.       for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);  
96.   
97.       if (i < 0) {  
98.   
99.          OUTPUT(j);  
100.   
101.          j += bmGs[0];  
102.   
103.       }  
104.   
105.       else  
106.   
107.          j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);  
108.   
109.    }  
110.   
111. }