在用於查找子字元串的算法當中，BM（Boyer-Moore）算法是目前被認為最高效的字元串搜尋算法，它由Bob Boyer和J Strother Moore設計於1977年。 一般情況下，比KMP算法快3-5倍。該算法常用於文本編輯器中的搜尋匹配功能，比如大家所熟知的GNU grep命令使用的就是該算法，這也是GNU grep比BSD grep快的一個重要原因。
基本介紹
- 中文名：博伊爾-摩爾算法
- 外文名：Boyer-Moore Algorithm
- 提出者： Bob Boyer和J Strother Moore
- 提出時間：1977年
- 套用學科：計算機科學
- 適用領域範圍：字元串搜尋
主要特徵,算法基本思想,字元風暴,理論探討,壞字元算法,好後綴算法,移動規則,具體執行,壞字元bmBc[],好後綴bmGs[],計算suff[],完整C代碼,
主要特徵
假設文本串text長度為n，模式串pattern長度為m，BM算法的主要特徵為：
-從右往左進行比較匹配（一般的字元串搜尋算法如KMP都是從從左往右進行匹配）；
-算法分為兩個階段：預處理階段和搜尋階段；
-預處理階段時間和空間複雜度都是是O(m+)，是字元集大小，一般為256；
-搜尋階段時間複雜度是O(mn)；
-當模式串是非周期性的，在最壞的情況下算法需要進行3n次字元比較操作；
-算法在最好的情況下達到O(n/m)，比如在文本串b中搜尋模式串ab ，只需要n/m次比較。
算法基本思想
常規的匹配算法移動模式串的時候是從左到右，而進行比較的時候也是從左到右的，基本框架是：
j = 0;while (j <= (strlen(text)-strlen(pattern))){ for (i = 0; i < strlen(pattern) && pattern[i] == text[i+j]; ++i); if (i == strlen(pattern)) { Match; break; } else ++j; }而BM算法在移動模式串的時候是從左到右，而進行比較的時候是從右到左的，基本框架是：
j = 0;while（j <= (strlen(text)-strlen(pattern))）{ for (i = strlen(pattern); i >= 0 && pattern[i] == text[i + j]; --i); if (i < 0)) { Match; break; } else j += BM(); }BM算法的精華就在於BM(text, pattern),也就是BM算法當不匹配的時候一次性可以跳過不止一個字元。即它不需要對被搜尋的字元串中的字元進行逐一比較，而會跳過其中某些部分。通常搜尋關鍵字越長，算法速度越快。它的效率來自於這樣的事實：對於每一次失敗的匹配嘗試，算法都能夠使用這些信息來排除儘可能多的無法匹配的位置。即它充分利用待搜尋字元串的一些特徵，加快了搜尋的步驟。
BM算法實際上包含兩個並行的算法（也就是兩個啟發策略）：壞字元算法（bad-character shift）和好後綴算法（good-suffix shift）。這兩種算法的目的就是讓模式串每次向右移動儘可能大的距離（即上面的BM()儘可能大）。
字元風暴
大家來頭腦風暴下：如何加快字元串搜尋？舉個很簡單的例子，如下圖所示，navie表示一般做法，逐個進行比對，從右向左，最後一個字元c與text中的d不匹配，pattern右移一位。但大家看一下這個d有什麼特徵？pattern中沒有d，因此你不管右移1、2、3、4位肯定還是不匹配，何必花這個功夫呢？直接右移5（strlen(pattern)）位再進行比對不是更好嗎？好，就這樣做，右移5位後，text中的b與pattern中的c比較，發現還是不同，這時咋辦？b在pattern中有所以不能一下右移5位了，難道直接右移一位嗎？No，可以直接將pattern中的b右移到text中b的位置進行比對，但是pattern中有兩個b，右移哪個b呢？保險的辦法是用最右邊的b與text進行比對，為啥？下圖說的很清楚了，用最左邊的b太激進了，容易漏掉真正的匹配，圖中用最右邊的b後發現正好所有的都匹配成功了，如果用最左邊的不就錯過了這個匹配項嗎？這個啟發式搜尋就是BM算法做的。
But, 如果遇到下面這樣的情況，開始pattern中的c和text中的b不匹配，Ok，按上面的規則將pattern右移直至最右邊的b與text的b對齊進行比對。再將pattern中的c與text中的c進行比對，匹配繼續往左比對，直到位置3處pattern中的a與text中的b不匹配了，按上面講的啟發式規則應該將pattern中最右邊的b與text的b對齊，可這時發現啥了？pattern走了回頭路，幹嗎？當然不乾，才不要那么傻，針對這種情況，只需要將pattern簡單的右移一步即可，堅持不走回頭路！
好了，這就是所謂的“壞字元算法”，簡單吧，通俗易懂吧，上面用紅色粗體字標註出來的b就是“壞字元”，即不匹配的字元，壞字元是針對text的。
BM難道就這么簡單？就一個啟發式規則就搞定了？當然不是了，大家再次頭腦風暴一下，有沒有其他加快字元串搜尋的方法呢？比如下面的例子
一開始利用了壞字元算法一下移了4位，不錯，接下來遇到了回頭路，沒辦法只能保守移一位，但真的就只能移一位嗎？No，因為pattern中前面其他位置也有剛剛匹配成功的後綴ab，那么將pattern前面的ab右移到text剛匹配成功的ab對齊繼續往前匹配不是更好嗎？這樣就可以一次性右移兩位了，很好的有一個啟發式搜尋規則啊。有人可能想：要是前面沒已經匹配成功的後綴咋辦？是不是就無效了？不完全是，這要看情況了，比如下面這個例子。
cbab這個後綴已經成功匹配，然後b沒成功，而pattern前面也沒發現cbab這樣的串，這樣就直接保守移一位？No，前面有ab啊，這是cbab後綴的一部分，也可以好好利用，直接將pattern前面的ab右移到text已經匹配成功的ab位置處繼續往前匹配，這樣一下子就右移了四位，很好。當然，如果前面完全沒已經匹配成功的後綴或部分後綴，比如最前面的babac，那就真的不能利用了。
好了，這就是所謂的“好後綴算法”，簡單吧，通俗易懂吧，上面用紅色字標註出來的ab（前面例子）和cbab（上面例子）就是“好後綴”，好後綴是針對pattern的。
下面，最後再舉個例子說明啥是壞字元，啥是好後綴。
主串 : mahtavaatalomaisema omalomailuun
模式串: maisemaomaloma
壞字元：主串中的“t”為壞字元。
好後綴：模式串中的aloma為“好後綴”。
BM就這么簡單？是的，容易理解但並不是每個人都能想到的兩個啟發式搜尋規則就造就了BM這樣一個優秀的算法。那么又有個問題？這兩個算法怎么運用，一下壞字元的，一下好後綴的，什麼時候該用壞字元？什麼時候該用好後綴呢？很好的問題，這就要看哪個右移的位數多了，比如上面的例子，一開始如果用好後綴的話只能移一位而用壞字元就能右移三位，此時當然選擇壞字元算法了。接下來如果繼續用壞字元則只能右移一位而用好後綴就能一下右移四位，這時候你說用啥呢？So，這兩個算法是“並行”的，哪個大用哪個。
光用例子說明當然不夠，太淺了，而且還不一定能完全覆蓋所有情況，不精確。下面就開始真正的理論探討了。
理論探討
壞字元算法
當出現一個壞字元時, BM算法向右移動模式串, 讓模式串中最靠右的對應字元與壞字元相對，然後繼續匹配。壞字元算法有兩種情況。
Case1：模式串中有對應的壞字元時，讓模式串中最靠右的對應字元與壞字元相對（PS：BM不可能走回頭路，因為若是回頭路，則移動距離就是負數了，肯定不是最大移動步數了），如下圖。
Case2：模式串中不存在壞字元，很好，直接右移整個模式串長度這么大步數，如下圖。
好後綴算法
如果程式匹配了一個好後綴, 並且在模式中還有另外一個相同的後綴或後綴的部分, 那把下一個後綴或部分移動到當前後綴位置。假如說，pattern的後u個字元和text都已經匹配了，但是接下來的一個字元不匹配，我需要移動才能匹配。如果說後u個字元在pattern其他位置也出現過或部分出現，我們將pattern右移到前面的u個字元或部分和最後的u個字元或部分相同，如果說後u個字元在pattern其他位置完全沒有出現，很好，直接右移整個pattern。這樣，好後綴算法有三種情況，如下圖所示：
Case1：模式串中有子串和好後綴完全匹配，則將最靠右的那個子串移動到好後綴的位置繼續進行匹配。
Case2：如果不存在和好後綴完全匹配的子串，則在好後綴中找到具有如下特徵的最長子串,使得P[m-s…m]=P[0…s]。
Case3：如果完全不存在和好後綴匹配的子串，則右移整個模式串。
移動規則
BM算法的移動規則是：
將3中算法基本框架中的j += BM()，換成j += MAX（shift（好後綴），shift（壞字元）），即BM算法是每次向右移動模式串的距離是，按照好後綴算法和壞字元算法計算得到的最大值。shift（好後綴）和shift（壞字元）通過模式串的預處理數組的簡單計算得到。壞字元算法的預處理數組是bmBc[]，好後綴算法的預處理數組是bmGs[]。
具體執行
BM算法子串比較失配時，按壞字元算法計算pattern需要右移的距離，要藉助bmBc數組，而按好後綴算法計算pattern右移的距離則要藉助bmGs數組。
壞字元bmBc[]
這個計算應該很容易，似乎只需要bmBc[i] = m - 1 - i就行了，但這樣是不對的，因為i位置處的字元可能在pattern中多處出現（如下圖所示），而我們需要的是最右邊的位置，這樣就需要每次循環判斷了，非常麻煩，性能差。這裡有個小技巧，就是使用字元作為下標而不是位置數字作為下標。這樣只需要遍歷一遍即可，這貌似是空間換時間的做法，但如果是純8位字元也只需要256個空間大小，而且對於大模式，可能本身長度就超過了256，所以這樣做是值得的（這也是為什麼數據越大，BM算法越高效的原因之一）。
如前所述，bmBc[]的計算分兩種情況，與前一一對應。
Case1：字元在模式串中有出現，bmBc['v']表示字元v在模式串中最後一次出現的位置，距離模式串串尾的長度，如上圖所示。
Case2：字元在模式串中沒有出現，如模式串中沒有字元v，則BmBc['v'] = strlen(pattern)。
C語言代碼：
void PreBmBc(char *pattern, int m, int bmBc[]){ int i; for (i = 0; i < MAX_CHAR; i++) bmBc[i] = m; for (i = 0; i < m - 1; i++) bmBc[pattern[i]] = m - 1 - i; /* printf(""bmBc[]:); for (i = 0; i < m; i++) printf("%d ",bmBc[pattern[i]]); printf("\n"); */}計算pattern需要右移的距離，要藉助bmBc數組，那么bmBc的值是不是就是pattern實際要右移的距離呢？No，想想也不是，比如前面舉例說到利用bmBc算法還可能走回頭路，也就是右移的距離是負數，而bmBc的值絕對不可能是負數，所以兩者不相等。那么pattern實際右移的距離怎么算呢？這個就要看text中壞字元的位置了，前面說過壞字元算法是針對text的，還是看圖吧，一目了然。圖中v是text中的壞字元（對應位置i+j）,在pattern中對應不匹配的位置為i，那么pattern實際要右移的距離就是：bmBc['v'] - m + 1 + i。
好後綴bmGs[]
這裡bmGs[]的下標是數字而不是字元了，表示字元在pattern中位置。
如前所述，bmGs數組的計算分三種情況，與前一一對應。假設圖中好後綴長度用數組suff[]表示。
Case1：對應好後綴算法case1，如下圖，j是好後綴之前的那個位置。
Case2：對應好後綴算法case2：如下圖所示：
Case3：對應與好後綴算法case3，bmGs[i] = strlen（pattern）= m
這樣就清晰了，代碼編寫也比較簡單：
void PreBmGs(char *pattern, int m, int bmGs[]){ int i, j; int suff[SIZE]; // 計算後綴數組 suffix(pattern, m, suff); // 先全部賦值為m，包含Case3 for (i = 0; i < m; i++) bmGs[i] = m; // Case2 j = 0; for (i = m - 1; i >= 0; i--) { if (i + 1 == suff[i]) { for (;j < m - 1 - i; j++) { if (m == bmGs[j]) bmGs[j] = m - 1 - i; } } } // Case1 for (i = 0; i <= m - 2; i++) bmGs[m - 1 - suff[i]] = m - 1 - i; print(bmGs, m , "bmGs[]");}計算suff[]
在計算bmGc數組時，為提高效率，先計算輔助數組suff[]表示好後綴的長度。
suff數組的定義：m是pattern的長度
a. suffix[m-1] = m;
b. suffix[i] = k
for [ pattern[i-k+1] ....,pattern[i]] == [pattern[m-1-k+1]，pattern[m-1]]
看上去有些晦澀難懂，實際上suff[i]就是求pattern中以i位置字元為後綴和以最後一個字元為後綴的公共後綴串的長度。不知道這樣說清楚了沒有，還是舉個例子吧：
i : 0 1 2 3 4 5 6 7
pattern: b c a b a b a b
pattern: b c a b a b a b
當i=7時，按定義suff[7] = strlen(pattern) = 8
當i=6時，以pattern[6]為後綴的後綴串為bcababa，以最後一個字元b為後綴的後綴串為bcababab，兩者沒有公共後綴串，所以suff[6] = 0
當i=5時，以pattern[5]為後綴的後綴串為bcabab，以最後一個字元b為後綴的後綴串為bcababab，兩者的公共後綴串為abab，所以suff[5] = 4
以此類推……
當i=0時，以pattern[0]為後綴的後綴串為b，以最後一個字元b為後綴的後綴串為bcababab，兩者的公共後綴串為b，所以suff[0] = 1
這樣看來代碼也很好寫：
void suffix_old(char *pattern, int m, int suff[]){ int i, j; suff[m - 1] = m; for (i = m - 2; i >= 0; i--) { j = i; while (j >= 0 && pattern[j] == pattern[m -1 - i + j]) j--; suff[i] = i - j; }}這樣可能就萬事大吉了，可是總有人對這個算法不滿意，感覺太暴力了，於是有聰明人想出一種方法，對上述常規方法進行改進。基本的掃描都是從右向左，改進的地方就是利用了已經計算得到的suff[]值，計算現在正在計算的suff[]值。具體怎么利用，看下圖：
i是當前正準備計算suff[]值的那個位置。
f是上一個成功進行匹配的起始位置（不是每個位置都能進行成功匹配的， 實際上能夠進行成功匹配的位置並不多）。
g是上一次進行成功匹配的失配位置。
如果i在g和f之間，那么一定有P[i]=P[m-1-f+i]；並且如果suff[m-1-f+i] < i-g, 則suff[i] = suff[m-1-f+i]，這不就利用了前面的suff了嗎。
PS：這裡有些人可能覺得應該是suff[m-1-f+i] <= i - g，因為若suff[m-1-f+i] = i - g，還是沒超過suff[f]的範圍，依然可以利用前面的suff[]，但這是錯誤的，比如一個極端的例子：
i ：0 1 2 3 4 5 6 7 8 9
pattern：a a a a a b a a a a
pattern：a a a a a b a a a a
suff[4] = 4，這裡f=4，g=0，當i=3時，這時suff[m-1-f+i]=suff[8]=3，而suff[3]=4，兩者不相等，因為上一次的失配位置g可能會在這次得到匹配。
好了，這樣解釋過後，代碼也比較簡單：
void suffix(char *pattern, int m, int suff[]){ int f, g, i; suff[m - 1] = m; g = m - 1; for (i = m - 2; i >= 0; --i) { if (i > g && suff[i + m - 1 - f] < i - g) suff[i] = suff[i + m - 1 - f]; else { if (i < g) g = i; f = i; while (g >= 0 && pattern[g] == pattern[g + m - 1 - f]) --g; suff[i] = f - g; } } //print(suff, m, "suff[]");}完整C代碼
#include <stdio.h>#include <string.h>#define MAX_CHAR 256#define SIZE 256#define MAX(x, y) (x) > (y) ? (x) : (y)void BoyerMoore(char *pattern, int m, char *text, int n);int main(){ char text[256], pattern[256]; while (1) { puts("Please input the text and the pattern:(input Q to quit.)"); gets(text); if (!strcmp(text, "Q") || ! strcmp(text, "q")) break; gets(pattern); //printf("%s\n", text); //printf("%s\n", pattern); BoyerMoore(pattern, strlen(pattern), text, strlen(text)); printf("\n"); } return 0;}void print(int *array, int n, char *arrayName){ int i; printf("%s:", arrayName); for (i = 0; i < n; i++) printf("%d ", array[i]); printf("\n");}void PreBmBc(char *pattern, int m, int bmBc[]){ int i; for (i = 0; i < MAX_CHAR; i++) bmBc[i] = m; for (i = 0; i < m - 1; i++) bmBc[pattern[i]] = m - 1 - i; /* printf(""bmBc[]:); for (i = 0; i < m; i++) printf("%d ",bmBc[pattern[i]]); printf("\n"); */}void suffix_old(char *pattern, int m, int suff[]){ int i, j; suff[m - 1] = m; for (i = m - 2; i >= 0; i--) { j = i; while (j >= 0 && pattern[j] == pattern[m -1 - i + j]) j--; suff[i] = i - j; }}void suffix(char *pattern, int m, int suff[]) //改進計算suffix方法{ int f, g, i; suff[m - 1] = m; g = m - 1; for (i = m - 2; i >= 0; --i) { if (i > g && suff[i + m - 1 - f] < i - g) suff[i] = suff[i + m - 1 - f]; else { if (i < g) g = i; f = i; while (g >= 0 && pattern[g] == pattern[g + m - 1 - f]) --g; suff[i] = f - g; } } //print(suff, m, "suff[]");}void PreBmGs(char *pattern, int m, int bmGs[]){ int i, j; int suff[SIZE]; // 計算後綴數組 suffix(pattern, m, suff); // 先全部賦值為m，包含Case3 for (i = 0; i < m; i++) bmGs[i] = m; // Case2 j = 0; for (i = m - 1; i >= 0; i--) { if (i + 1 == suff[i]) { for (;j < m - 1 - i; j++) { if (m == bmGs[j]) bmGs[j] = m - 1 - i; } } } // Case1 for (i = 0; i <= m - 2; i++) bmGs[m - 1 - suff[i]] = m - 1 - i; print(bmGs, m , "bmGs[]");}void BoyerMoore(char *pattern, int m, char *text, int n){ int i, j, bmBc[MAX_CHAR], bmGs[SIZE]; // Preprocessing PreBmBc(pattern, m, bmBc); PreBmGs(pattern, m, bmGs); // Searching j = 0; while (j <= n - m) { for (i = m - 1; i >= 0 && pattern[i] == text[i + j]; i--); if (i < 0) { printf("Find it, the position is %d\n", j); j += bmGs[0]; return ; } else j += MAX(bmBc[text[i + j]] - m + 1 + i, bmGs[i]); } printf("No find.\n");}