BF 算法

BF 算法中的 BF 是 Brute Force 的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法。这种算法的字符串匹配方式比较简单，相应的性能也不高。

在开始讲解算法之前，你需要知道两个概念，一个是主串，另一个模式串。比方说，我们在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串。我们把主串的长度记作 n，模式串的长度记作 m。因为我们是在主串中查找模式串，所以 n>m，否则匹配算法一定是无解的。

BF 算法的思想可以用一句话来概括，那就是，在主串中，检查起始位置分别是 0、1、2....n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。

BF 算法的时间复杂度很高，是 O(n*m)，但在实际的开发中，它却是一个比较常用的字符串匹配算法，这其中有两个原因，第一个原因是在实际的软件开发中，大部分情况下，模式串和主串的长度都不会太长；第二个原因是朴素字符串匹配算法思想简单，代码实现也非常简单，这样的代码出错的概率也会低很多，相应的，维护和改动的成本也很低。

RK 算法

RK 算法的全称叫 Rabin-Karp 算法，是由它的两位发明者 Rabin 和 Karp 的名字来命名的。这种算法是基于朴素的字符串匹配算法的一种改造，引入哈希算法，从而降低了算法的时间复杂度。

RK 算法的思路是这样的：我们通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了（这里需要考虑哈希冲突的问题，即设计合理的哈希算法）。因为哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模式串和子串比较的效率就提高了。因为可能存在哈希冲突的问题，所以更安全的方式是在哈希值相同的情况下，再对原字符串进行比较。

BM 算法

BM（Boyer-Moore）算法，是一种非常高效的字符串匹配算法，相应的，实现上也会更复杂。

BM 算法包含两部分，分别是坏字符规则（bad character rule）和好后缀规则（good suffix shift）。

什么是坏字符？从模式串的末尾往前倒着匹配，当发现某个字符没法匹配的时候，就把这个没有匹配的字符叫作坏字符（主串中的字符）。

坏字符规则指，我们用坏字符在模式串中查找，根据匹配的结果，每次滑动若干位，直至比较结束。具体滑动多少位呢？当发生不匹配的时候，我们把坏字符对应的模式串中的字符下标记作 si。如果坏字符在模式串中存在，我们把这个坏字符在模式串中的下标记作 xi。如果不存在，我们把 xi 记作 -1。那模式串往后移动的位数就等于 si-xi。（注意，我这里说的下标，都是字符在模式串的下标）。简而言之，当遇到坏字符时，要计算往后移动的位数 si-xi，其中 xi 的计算是重点。

单纯使用坏字符规则还是不够的，因为根据 si-xi 计算出来的移动位数，有可能是负数，不但不会向后滑动模式串，还有可能倒退。所以，BM 算法还需要用到“好后缀规则”。

好后缀规则实际上跟坏字符规则的思路很类似。我们把已经匹配的 bc 叫作好后缀，记作{u}。我们拿它在模式串中查找，如果找到了另一个跟{u}相匹配的子串{u}，那我们就将模式串滑动到子串{u}与主串中{u}对齐的位置。如果好后缀在模式串中不存在可匹配的子串，那在我们一步一步往后滑动模式串的过程中，只要主串中的{u}与模式串有重合，那肯定就无法完全匹配。但是当模式串滑动到前缀与主串中{u}的后缀有部分重合的时候，并且重合的部分相等的时候，就有可能会存在完全匹配的情况。因此，我们不仅要看好后缀在模式串中，是否有另一个匹配的子串，我们还要考察好后缀的后缀子串，是否存在跟模式串的前缀子串匹配的。所谓某个字符串 s 的后缀子串，就是最后一个字符跟 s 对齐的子串，比如 abc 的后缀子串就包括 c, bc。所谓前缀子串，就是起始字符跟 s 对齐的子串，我们需要从好后缀的后缀子串中，找一个最长的并且能跟模式串的前缀子串匹配的位置。好后缀处理规则中最核心的内容包括两点：

• 在模式串中，查找跟好后缀匹配的另一个子串；
• 在好后缀的后缀子串中，查找最长的、能跟模式串前缀子串匹配的后缀子串；

BM 算法核心思想是，利用模式串本身的特点，在模式串中某个字符与主串不能匹配的时候，将模式串往后多滑动几位，以此来减少不必要的字符比较，提高匹配的效率。

KMP 算法

KMP 算法是根据三位作者（D.E.Knuth，J.H.Morris 和 V.R.Pratt）的名字来命名的，算法的全称是 Knuth Morris Pratt 算法，简称为 KMP 算法。KMP 算法的核心思想和 BM 算法非常相近。我们假设主串是 a，模式串是 b。在模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，我们希望找到一些规律，可以将模式串往后多滑动几位，跳过那些肯定不会匹配的情况。

KMP 算法的框架代码如下:

// a, b分别是主串和模式串；n, m分别是主串和模式串的长度。
public static int kmp(char[] a, int n, char[] b, int m) {
  int[] next = getNexts(b, m);
  int j = 0;
  for (int i = 0; i < n; ++i) {
    while (j > 0 && a[i] != b[j]) { // 一直找到a[i]和b[j]
      j = next[j - 1] + 1;
    }
    if (a[i] == b[j]) {
      ++j;
    }
    if (j == m) { // 找到匹配模式串的了
      return i - m + 1;
    }
  }
  return -1;
}

其中，next 数组的计算是整个实现上最复杂的部分，代码实现如下：

// b表示模式串，m表示模式串的长度
private static int[] getNexts(char[] b, int m) {
  int[] next = new int[m];
  next[0] = -1;
  int k = -1;
  for (int i = 1; i < m; ++i) {
    while (k != -1 && b[k + 1] != b[i]) {
      k = next[k];
    }
    if (b[k + 1] == b[i]) {
      ++k;
    }
    next[i] = k;
  }
  return next;
}

KMP 算法只需要一个额外的 next 数组，数组的大小跟模式串相同。所以KMP 算法的空间复杂度是 O(m)，m 表示模式串的长度。而时间复杂度的分析则需要从两部分来分析，第一部分是构建 next 数组，第二部分才是借助 next 数组匹配。第一部分的时间复杂度为 O(m)，第二部分的时间复杂度是 O(n)，综合这两部分的时间复杂度，KMP 算法的时间复杂度就是 O(m+n)。