經典單模式匹配算法：KMP、BM；經典多模式匹配算法：AC、Wu-Manber。貌似實用中，KMP跟C庫strstr()效率相當，而BM能快上3x-5x。于是小女不才花了小天的功夫來研究這個BM算法。BM如何快速匹配模式？它怎么跳躍地？我今兒一定要把大家伙兒講明白了，講不明白您佬跟帖，我買單，包教包會。

模式，記為pat，用j作為索引; 文本，記為string（或text），用i作為索引。

Input: pat, string Algorithm: BM，在string中進行pat匹配。 Output: 匹配上則返回匹配地址，否則返回-1。

圖1

圖1是一簡單示意圖。左對齊pat與string，小指針（記為p）指向對齊后的右end，開始比對。如果pat[p]= string[p]，那么小指針往左挪（挪到左end說明匹配上了），否則就要滑動pat進行重新對齊，重新對齊后，小指針當然也要跟著溜到末位進行重新比對。那么究竟怎么個滑法？分四個case：

1.       末位不匹配，且string[p]在pat中不存在，那么pat可以一下子右移patlen個單位。因為你一個一個右移只是徒勞，沒人跟string[i]能匹配上。比如，圖1中F與T不匹配，且F在pat中不存在，那么我們可以把pat右滑patlen，小指針也跟著移至末位，移動后如圖2所示。

圖2

2.       末位不匹配，但string[p]在pat中存在（如果有多個，那就找最靠右的那個），距離pat右端為delta1。那么右移pat使得它們對齊。比如，圖2中減號與T不匹配，但減號存在于pat中，數數知道delta1=4，那就右移pat使得兩個減號對上，移動后如圖3所示。

圖3

總結：從1、2可以得到， dealta1 = patlen,  當string[p]在patlen中不存在       = patlen – 最右邊那個string[p]的位置，   當string[p]在patlen中存在   delta1()是所有字符的函數，例如pat和string對應26個字母，那么dealta1(‘a’)…dealta1(‘z’)。只需掃描一下pat，就能記錄下值了。別地兒管這個叫“壞字符規則”。

3.       末m位都匹配上了(m<patlen)，但未匹配完，如圖4中的三個示例，末m (m=4)位匹配上了，小指針指向的兩個字符都發生了mismatch，記為mismatched char。

1)        圖4中示例1，string中的c在pat中的最右出現居然還在小指針靠后的位置，總不至于為了讓string中c跟pat中最右c匹配上就把pat往回倒滑一個位置吧，才不要那么瓜，遇到這種情況就讓pat往右滑k=1個位置好了，此時小指針為了滑至最后需要滑k+m=5個位置。

2)        圖4中示例2，string中c在pat中的最右出現在小指針前面，那好吧，就讓此a跟彼a對齊吧。即讓pat向右滑k=delta1(‘a’)-m=6-4=2個位置，此時小指針為了滑至最后需要滑k+m={dealta1(‘a’)-m}+m=dealta1(‘a’)=6個位置。

3)        圖4中示例3，string中y在pat中未出現。那么將patlen向右移k=delta1(‘y’)-m=6-4=2個位置，此時小指針為了滑至最后需要滑dealta1(‘y’)=6個位置。

圖4

總結：從3可以得到， pat右移位數 = 1，  當示例1             = k =delta1(‘char’)-m， 當示例2、3。. String右移位數 = k+m

4.         照著3那么移挺對也挺好地，但某些情況下，如圖7的情況，能不能讓pat右移地更快呢？圖7示例1，按3的分析只能將pat右滑1位，實際上我們可以放心右滑pat成示例2的樣子，然后再將小指針移至末位開始匹配。

圖7

下面的部分會比較繞，請讀者用心看。圖7示例1，末m(m=3)位即abc匹配上了，記為subpat，那么pat中出現的最右abc且不由mismatched char引導的位置，記為末subpat的“重現位置”，如”gabcfabceabceabc”重現位置應該是f引導的subpat，可以理解么？因為g引導的subpat不是最右的，倒數第2個e引導的subpat是由mismatched char引導的。

于是我們引入delta2(j)函數，j是發生mismatched的位置，我們記subpat的“重現位置”為rpr(j)，那么pat應該右移k，相應地string右移k+m。如何計算k?

預處理pat，j=1…patlen，那么rpr(j)是指以j為mismatched的位置，以j+1…patlen為subpat的“重現位置”。 rpr(j) = max{k| k<=patlen && [pat(j+1) ... pat(patlen)]= [pat(k) ... pat(k+patlen-j-1)]           && (k<=1 || pat(k-1) != pat(j) }    rpr(patlen)=patlen。 其中對于“=”的判斷，要么pat(x)=pat(j)要么pat(x)=NULL要么pat(y)=NULL。 舉個例子就明白了：   下面解釋rpr(j)：   上圖您能接受么？呵呵，$表示空元素。例如j=1時，要跟pat[j+1]…pat[patlen]匹配，那么pat[k]…p[k+patlen-j-1]最多就是如圖所示，此時k+patlen-j-1=3即k+9-1-1=3，于是k= -4，k再大您可以試試，不好使了就。其它依此類推。讀者可練習求一下下面這個rpr(j)。

OK，如何求滑動距離k呢？現在小指針指在j的位置上，“重現位置”在rpr(j)，那么k=j+1-rpr(j)，小指針需要挪至最后所以k+m={j+1-rpr(j)}+{patlen-j}=patlen+1-rpr(j)，即有delta2(j)=patlen+1-rpr(j)。

總結：從3、4可以得到， 末m個元素已經匹配的情況，string需要右滑多少呢？計算delta1(string(i)),delta2(j)，誰大取誰，就說滑的越多越好，反正都有匹配不上的理由。

OK，現在給出算法偽碼，加油，就快結束了：

實現上，可以更快一點。看到delta0()不要驚訝，它和delta1()基本相同，除了delta0(pat(patlen))被設置為>stringlen+patlen的一個數。因為1、2兩種case在匹配中遇到的頻率很高，我們抽出fast部分，匹配時間的70%-80%都在走fast部分。自己舉個例子把偽碼過一遍，不明白地方跟帖。

別地兒都稱 “壞字符規則” “好后綴規則”，嘛回事？fatdog如是寫：

哈哈，好不好笑？壞字符規則就是我們的delta1(char)計算，好后綴規則就是我們的delta2(j)計算，本來就一碼事兒。

//預處理 計算bmGS[]和bmBC[]表；//BM的Good Suffix、Bad Character while(text<textend) {      //從當前匹配點text開始匹配關鍵詞      for(i=m;(i>=0)&&(text[i]=pattern[i]);i--)          ;      if(i<0)      {          //匹配成功          報告一個成功的匹配;          text+=bmGS[0];//選擇下一個匹配入口點      }      else  //匹配失敗，此時i指示著不匹配的位置點text[i]!=pat[i]      {          //使用兩種啟發式方法選擇下一個匹配入口點          text+=Max(bmGS[i]-m+1,bmBC[i]);      } }

BM通常是sublinear的復雜度，最好O(n/m)，最壞O(n)。一般會匹配string中的c*(i+patlen)個字符，其中c<1，并且patlen越大c越小，通常在longer pat下BM表現更出色。