C++BM算法

bm算法是一種非常著名的字元串查找算法：

在字元串查找算法中，最著名的兩個是kmp算法（knuth-morris-pratt)和bm算法（boyer-moore)。兩個算法在最壞情況下均具有線性的查找時間。但是在實用上，kmp算法并不比最簡單的c庫函數strstr()快多少，而bm算法則往往比kmp算法快上3－5倍。

下面我們介紹一下bm算法：

1,bm算法是boyer-moore算法的簡稱，由boyer 和moore提出. 

2，bm算法也是一種快速串比對算法，bm算法與kmp算法的主要差別是比對操作的方向不同。雖然bm算法僅把比對操作的字元比較順序改為從右向左，但比對發生失敗時，模式t右移的計算方法卻發生了較大的變化. 

3,滑動距離函數: 

為友善讨論，bm算法的關鍵是，對給定的模式t＝＂t0t1…tm＂定義一個從字元到正整數的映射： 

dist ：ｃ－＞｛1,2,…,m+1｝ 

函數dist稱為滑動距離函數，它給出了正文中可能出現的任意字元在模式中的位置。函數dist定義如下： 

dist(c) = m-j  j為c在模式中的下标，以後面的為準 

dist(c) = m+1  若c不在模式中或c = tm 

例如，t＝＂pattern＂，則dist（p）= 6 – 0 = 6, dist（a）= 6 – 1 =5, dist（t）=

6 – 3 =3，dist（e）= 2， dist（r）= 1, dist（n）= 6 + 1 = 7。 

4,bm算法的基本思想是：假設将主串中自位置i起往左的一個子串與模式進行從右到左的比對過程中，若發現不比對，則下次應從主串的i + dist(si)位置開始重新進行新一輪的比對，其效果相當于把模式和主串向右滑過一段距離dist（si），即跳過dist（si）個字元而無需進行比較。 

如這樣一個例子：

從findinahaystackneedleina中查找needle的過程：

i    j    00    01    02    03    04    05    06    07    08    09    10    11    12     13    14    15    16    17    18    19

   20    21    22    23

          f      i       n      d     i      n    

a      h     a      y    s      t      a       c     k      n    e      e

    d      l     e      i       n      a

0   5   n     e      e      d     l       e

5   5                                           n     e      e      d     l      e

11 4                                                                                           n       e       e     d    l

    e

15 0                                                                                                                             n

    e      e     d     l     e

排版不是很好排，請大家見諒

第一步：i=5，j=5失敗 dist（n）= 5 是以右移到5+5=10處

第二步：i=10，j=5失敗 無dist(s) 是以右移到10+6 =16處

第三步：i=15，j=4失敗 dist(n) = 5 是以右移到15+5 = 20處比對成功

執行個體代碼: