字符串匹配—BM算法

单模式串匹配算法中BM（Boyer-Moore）算法算是很难理解的算法了，不过性能高效，据说比KMP算法性能提升3到4倍，所以有必要学习下，才有可能在笔试或者面试中大显身手。
先看下BM算法原版简介

该算法从模式串的尾部开始匹配，且拥有在最坏情况下 O(N) 的时间复杂度。在算法介绍中，作者提出了好后缀规则(good-suffix shift)和坏字符规则(bad-character shift)。

坏字符规则（bad-character shift）

当文本串中的某个字符跟模式串的某个字符不匹配时，我们称文本串中的这个失配字符为坏字符，此时模式串需要向右移动，移动的位数 = 坏字符在模式串中的位置 - 坏字符在模式串中最右出现的位置。此外，如果"坏字符"不包含在模式串之中，则最右出现位置为 -1。坏字符针对的是文本串。

好后缀规则（good-suffix shift）

当字符失配时，后移位数 = 好后缀在模式串中的位置 - 好后缀在模式串上一次出现的位置，且如果好后缀在模式串中没有再次出现，则为 -1。好后缀针对的是模式串。

BM算法 的一个特点是当不匹配的时候 一次性可以跳过不止一个字符 。即它不需要对被搜索的字符串中的字符进行逐一比较，而会跳过其中某些部分。通常搜索关键字越长，算法速度越快。它的效率来自于这样的事实：对于每一次失败的匹配尝试，算法都能够使用这些信息来排除尽可能多的无法匹配的位置。

它充分利用待搜索字符串的 一些特征 ，加快了搜索的步骤。

那它是利用了什么特性去 排除尽可能多的无法匹配的位置 呢？

它是基于以下两个规则让模式串每次向右移动 尽可能大 的距离。

坏字符规则

坏字符出现的时候有两种情况进行讨论。

1、模式串中没有出现了文本串中的那个坏字符，将模式串直接整体对齐到这个字符的后方，继续比较。

2、模式串中有对应的坏字符时，让模式串中 最靠右 的对应字符与坏字符相对。

这句话有一个关键词是 最靠右。

思考一下为什么是 最靠右？

看图！

好后缀规则

1、如果模式串中存在已经匹配成功的好后缀，则把目标串与好后缀对齐，然后从模式串的最尾元素开始往前匹配。


2、如果无法找到匹配好的后缀，找一个匹配的最长的前缀，让目标串与最长的前缀对齐（如果这个前缀存在的话）。模式串[m-s，m] = 模式串[0，s] 。

3、如果完全不存在和好后缀匹配的子串，则右移整个模式串。

GIF动图演示

最终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;
}