字符串匹配——BM（Boyer-Moore）

BM算法采用了尾部比较的方法，具体来说就是：字符串与搜索词头部对齐，从尾部开始搜索，然后直接从尾部比较。
其定义了坏字符规则和好后缀规则。

坏字符规则

两者首次匹配时，尾部S与E不匹配，则称S为坏字符，此时在搜索词中无法搜索到坏字符S，因此直接将搜索词移动到S后

若坏字符P在搜索词中能够找到，则将字符串与搜索词中的P对齐。
因此坏字符规则可总结为：

1. 若搜索词中存在坏字符，则两者对齐
2. 若搜索词中不存在坏字符，则直接移动到坏字符后
   用公式表示为：

   后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置

若坏字符不存在与搜索词中，则上次出现位置为-1
其实就是：后移位数 = 搜索词长度 - 搜索词中上次出现的位置。上次出现的位置是从右往左寻找的。如坏字符B与搜索词ABABA，则上次出现的位置为从右往左的第二位B。

好后缀规则

**若字符串MPLE与搜索词匹配，则MPLE成为好后缀

而I与A不匹配，则I为坏字符，按照坏字符规则将移动 2-（-1）= 3位，但若按照好后缀规则：

后移位数 = 好后缀的位置 - 搜索词中的上一次出现位置

则移动位数为6 - 0 = 6位
所谓好后缀规则就是：

1. 若好后缀在搜索词中出现，则将两者对齐，若好后缀出现多次，则与最右侧的那个对齐
2. 若好后缀只出现一次，则寻找其最大子串作为好后缀。

接着取好后缀与坏字符中移动步数较大者作为最后移动步数。

// 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;
}

c++

//BM算法：字符串搜索
#include "stdafx.h"
#include<iostream>
#include<string>
#include<vector>
using namespace std;
vector<int> preBmBc(string ps);
int main()
{
    string ts = "HERE IS A SIMPLE EXAMPLE";
    string ps = "EXAMPLE";
    vector<int> matched;
    vector<int> BC = preBmBc(ps);//创建bad character数组
    //原始字符串与模式串长度
    int tlen = ts.size();
    int plen = ps.size();
    int tindex = 0;//ts索引
    while (tindex+plen <= tlen) {
        int badmove = 0;
        int goodmove = 0;
        for (size_t j = plen; j > 0; j--)
        {
            if (ts[tindex + j - 1] != ps[j - 1]) {
                badmove = BC[ts[tindex+j-1]]; //bad character移动步数
                cout <<"Move step:"<< badmove << endl;
                break;
            }
            if (j == 1) {//匹配到
                matched.push_back(tindex);
                tindex += plen - 1;
                continue;
            }
        }
        tindex += badmove;
    }
    for (size_t i = 0; i < matched.size(); i++)
    {
        cout << "matched at:" << matched[i] << endl;
    }
    system("pause");
    return 0;
}
//bad character数组，256
vector<int> preBmBc(string ps) {
    vector<int> BC(256, ps.size());
    for (size_t i = 0; i < ps.size(); i++)
    {
        BC[ps[i]] = ps.size() - i - 1;
    }
    return BC;
}

参考

https://juejin.im/post/5c87512f6fb9a049f571fcb5