單模式串匹配算法中BM（Boyer-Moore）算法算是很難理解的算法了，不過性能高效，據說比KMP算法性能提升3到4倍，suricata里面的單模式匹配就是用這種算法，所以有必要學習下，再把suricata的這部分代碼過一下還是不錯的。

一、BM算法原理

BM算法是1975年發明的,它是一種后匹配算法，我們普通的字符串匹配算法是從左向右的，BM算法是從右向做的，即先判斷模式串最后一個字符是否匹配，最后判斷模式串第一個字符是否匹配。

原來我們在BF算法中，如果模式串和主串不匹配，則將主串或模式串后移一位繼續匹配，BM算法根據模式串的特定規律，將后移一位的步子邁的更大一些，后移幾位。來看個圖簡單說明下，圖來自《數據結構與算法之美》課程：

但是如果我們仔細觀察，c字符在abd中不存在，那么abd可以直接移動到主串中c字符的后面再繼續匹配：

這樣移動的步數變大了，匹配起來肯定更快了。

BM算法根據模式串的特定規律，這里面的特定規律有兩種，一種是好后綴規則，一種是壞字符規則，初次看到這種規則的介紹后，心里嘀咕著這性能會好嗎，后面才發現經典的BM算法做了不少優化，所以性能高。下面分別介紹下好后綴規則（good suffix shift）和壞字符規則（bad character rule）。

1.1 BM壞字符規則

首先在BM算法里面何謂好壞那，匹配上的，我們稱為好，匹配不上的叫壞。按照剛才說的，BM算法是倒著匹配字符串的，我們在倒著匹配字符串的過程中，當我們發現某個字符沒法匹配的時候，我們把主串中這個沒法匹配的字符稱為壞字符。

我們發現在模式串中，字符c是不存在的，所以可以直接將模式字符串向后滑動3位繼續匹配。

滑動后，我們繼續匹配，發現主串中的字符a和模式串的d不匹配，這時候的情況和上一種不一樣，因為主串中的壞字符a在模式串中存在，則后移動2位，讓主串和模式串中的a對齊繼續匹配。那么每次后移多少位那，我們假設把匹配不到的壞字符的位置記作si，如果壞字符在模式串中存在，則壞字符在模式串中的位置記作xi，那么模式串后移為si-xi；如果壞字符在模式串中不存在，xi就為-1。上兩個圖中，第一個圖：si = 2，xi = -1 所以后移si-xi = 2+1 =3；第二個圖：si = 2，xi= 0所以后移的位置為si-xi=2。說明下如果壞字符在模式串中存在多個，那么應該選擇最后一個匹配壞字符的位置作為xi，這樣xi移動的步子就小，就不會遺漏應該匹配的情況。

單純利用壞字符規則是有問題的，因為si可以為0，xi可能大于0，這樣相減為負數，為此BM算法還增加了好后綴規則。

1.2 好后綴規則

模式串和主串匹配的部分叫做好后綴，如下圖：

如上圖，我們把匹配的部分bc 叫好后綴，記作{u}。我們拿它在模式串中查找，如果找到另一個跟{u}匹配的子串{u'},那么我們就將模式串滑動到子串{u'}與主串中{u}對齊的位置。

如果在模式串中找不到好后綴，那么直接將模式串滑動到主串中{u}后面，因為前面是沒有好后綴的{u}的。

但是上面的后移的位數是錯誤的，這里面有個規則，就是主串中{u}和模式串有重合，模式串移動前綴與主串中{u}第一次重合的部分，這個從直觀上來說也是比較好理解的。

好后綴規則3

用個示意圖標識：

說明，某個字符串s的后綴子串，就是最后一個字符和s對齊的子串，比如abc的后綴子串有c和bc。ab就不是，ab的最后一個字符不對齊；前綴子串，是開頭字符跟s對齊的子串，比如字符串abc的前綴子串有a和ab。我們需要從好后綴的后綴子串中，找一個最長的且跟模式串的前綴子串匹配的，假設是{v},然后將模式串移動到如圖位置：

。

總結下，好后綴有兩種移動方法： 1）如果好后綴子串{u}在模式串中存在{u*}完全匹配，則移動模式串，將最近的u*和主串對齊。 2）如果好后綴子串{u}在模式串中不存在，如果{u}的后綴子串有和模式串中的前綴子串匹配的{v‘} 則移動模式串和主串中的相應位置重合。 3）如果后綴子串{u}在模式串中不存在，且{u}的后綴子串在模式串中前綴子串沒有匹配的，則將模式串移動到匹配的好后綴子串后面即可。

二、算法實現

通過原理我們知道壞字符規則和好后綴規則都涉及到查找問題，如果查找性能不是很好，BM算法很難有好的性能，所以在工程實踐上，BM算法還是有不少技巧的。

我們在計算壞字符規則移動的位數的時候，需要通過si-xi來計算，si一般可以直接得到，xi怎么計算，xi為壞字符在模式串中的位置，如果一個個比對，性能肯定跟不上，假設字符集不是很大，我們可以用一個256數組，來記錄每個字符在模式串中的位置，數組下標可以直接對應字符的ASCII碼值，數組的值為字符在模式串中的位置：

說明下： 1）bc數組就是我們通過遍歷模式串得到的數組。 2）模式串里面有2個a，最終bc[97] = 3 標識壞字符a在模式串中的位置應該為3，這是因為壞字符在模式串中如果有多個匹配，只能用后面一個，這樣步字小一點。 97即為a的ascii值。

private static final int SIZE = 256; // 全局變量或成員變量

private void generateBC(char[] b, int m, int[] bc) {
  for (int i = 0; i < SIZE; ++i) {
    bc[i] = -1; // 初始化 bc
  }
  for (int i = 0; i < m; ++i) {
    int ascii = (int)b[i]; // 計算 b[i] 的 ASCII 值
    bc[ascii] = i;
  }
}

代碼比較簡單，先不考慮好字符規則，只用壞字符規則，這里面存在著移動位置為負數的問題，寫下BM算法的代碼：

public int bm(char[] a, int n, char[] b, int m) {
  int[] bc = new int[SIZE]; // 記錄模式串中每個字符最后出現的位置
  generateBC(b, m, bc); // 構建壞字符哈希表
  int i = 0; // i 表示主串與模式串對齊的第一個字符
  while (i <= n - m) {
    int j;
    for (j = m - 1; j >= 0; --j) { // 模式串從后往前匹配
      if (a[i+j] != b[j]) break; // 壞字符對應模式串中的下標是 j
    }
    if (j < 0) {
      return i; // 匹配成功，返回主串與模式串第一個匹配的字符的位置
    }
    // 這里等同于將模式串往后滑動 j-bc[(int)a[i+j]] 位
    i = i + (j - bc[(int)a[i+j]]); 
  }
  return -1;
}

好后綴規則的要求：

在模式串中查找跟好后綴匹配的另一個子串，如果查找到按照規則走，查找不到。
在好后綴的子串中，查找最長的，能夠跟模式串前綴子串匹配的后綴子串。

字符串的后綴子串，因為字符串結尾字符是固定的，只要存儲長度就可以推出后綴子串，如下圖：

后綴子串b 值為1，標識后綴子串，長度為1，我們就知道從后向前一個字節，依次類推。

現在我們引入關鍵的變量數組suffix數組，下標k標志后綴子串的長度，值為在模式串中除了好后綴子串在模式串中的匹配之前的匹配的后綴子串的位置：

同樣為了避免模式串滑動過頭，如果模式串中有多個子串跟后綴子串{u}匹配，那么suffix數組存的是模式串中最靠后的子串起始位置。

這樣還不夠，查找跟好后綴匹配的另一個子串，還要在好后綴的后綴子串中，查找最長的能夠跟模式串的前綴子串匹配的后綴子串。所以我們需要另一個boolean的prefix數組，來記錄模式串（也是好后綴的）的后綴子串是否能夠匹配模式串的前綴子串。

說明：

圖中后綴子串b，和模式字符串的前綴子串不匹配，因為匹配的話第一字符必須是c。
圖中只有cab這個后綴子串才和模式串的前綴子串相互匹配。
其他的類似。 suffix 和prefix數組的計算過程如下：

// b 表示模式串，m 表示長度，suffix，prefix 數組事先申請好了
private void generateGS(char[] b, int m, int[] suffix, boolean[] prefix) {
  for (int i = 0; i < m; ++i) { // 初始化
    suffix[i] = -1;
    prefix[i] = false;
  }
  for (int i = 0; i < m - 1; ++i) { // b[0, i]
    int j = i;
    int k = 0; // 公共后綴子串長度
    while (j >= 0 && b[j] == b[m-1-k]) { // 與 b[0, m-1] 求公共后綴子串
      --j;
      ++k;
      suffix[k] = j+1; //j+1 表示公共后綴子串在 b[0, i] 中的起始下標
    }
    i
    if (j == -1) prefix[k] = true; // 如果公共后綴子串也是模式串的前綴子串
  }
}

真實環境中，我們如何根據好后綴和壞字符的規則移動那。假設好后綴的長度是k。我們先拿到好后綴，在suffix數組中查找其匹配的子串，如果suffix[k]不等于-1 ，我們就將模式串向后移動j-suffix[k] +1 位（j標識壞字符串對應的模式串中字符的下標）。

如果suffix[k] = -1 ,標識模式串中不存在另一個跟好后綴子串片段，可以用下面規則來處理：好后綴的后綴子串b[r,m-1]（其中，r取值從j+2到m-1）的長度k = m-r，如果prefix[k]= true，標識長度為k的后綴子串，有可以匹配的前綴子串，我們可以把模式串后移r位。

如果兩條規則都沒有找到可以匹配的好后綴及其后綴子串的匹配的前綴子串，將整個模式串后移m位：

最終JAVA版本的完整代碼：

// a,b 表示主串和模式串；n，m 表示主串和模式串的長度。
public int bm(char[] a, int n, char[] b, int m) {
  int[] bc = new int[SIZE]; // 記錄模式串中每個字符最后出現的位置
  generateBC(b, m, bc); // 構建壞字符哈希表
  int[] suffix = new int[m];
  boolean[] prefix = new boolean[m];
  generateGS(b, m, suffix, prefix);
  int i = 0; // j 表示主串與模式串匹配的第一個字符
  while (i <= n - m) {
    int j;
    for (j = m - 1; j >= 0; --j) { // 模式串從后往前匹配
      if (a[i+j] != b[j]) break; // 壞字符對應模式串中的下標是 j
    }
    if (j < 0) {
      return i; // 匹配成功，返回主串與模式串第一個匹配的字符的位置
    }
    int x = j - bc[(int)a[i+j]];
    int y = 0;
    if (j < m-1) { // 如果有好后綴的話
      y = moveByGS(j, m, suffix, prefix);
    }
    i = i + Math.max(x, y);
  }
  return -1;
}

// j 表示壞字符對應的模式串中的字符下標 ; m 表示模式串長度
private int moveByGS(int j, int m, int[] suffix, boolean[] prefix) {
  int k = m - 1 - j; // 好后綴長度
  if (suffix[k] != -1) return j - suffix[k] +1;
  for (int r = j+2; r <= m-1; ++r) {
    if (prefix[m-r] == true) {
      return r;
    }
  }
  return m;
}

代碼實例

void preBmBc(char *x, int m, int bmBc[]) {
   int i;
 
   for (i = 0; i < ASIZE; ++i)
      bmBc[i] = m;
   for (i = 0; i < m - 1; ++i)
      bmBc[x[i]] = m - i - 1;
}
 
 
void suffixes(char *x, 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 && x[g] == x[g + m - 1 - f])
            --g;
         suff[i] = f - g;
      }
   }
}
 
void preBmGs(char *x, int m, int bmGs[]) {
   int i, j, suff[XSIZE];
 
   suffixes(x, m, suff);
 
   for (i = 0; i < m; ++i)
      bmGs[i] = m;
   j = 0;
   for (i = m - 1; i >= 0; --i)
      if (suff[i] == i + 1)
         for (; j < m - 1 - i; ++j)
            if (bmGs[j] == m)
               bmGs[j] = m - 1 - i;
   for (i = 0; i <= m - 2; ++i)
      bmGs[m - 1 - suff[i]] = m - 1 - i;
}
 
 
void BM(char *x, int m, char *y, int n) {
   int i, j, bmGs[XSIZE], bmBc[ASIZE];
 
   /* Preprocessing */
   preBmGs(x, m, bmGs);
   preBmBc(x, m, bmBc);
 
   /* Searching */
   j = 0;
   while (j <= n - m) {
      for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
      if (i < 0) {
         OUTPUT(j);
         j += bmGs[0];
      }
      else
         j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
   }
}