KMP算法

算法

记文本串为t，模式串为p，如下图：

假设已经匹配到了一部分，但是在箭头所指处，两字符不匹配。

对于朴素匹配算法，现在需要把串p往后移一步，再从头开始对字符一个个比较。

由于已匹配部分完全相同，所以两者有相同的A部分与B部分，那么如果模式串p中有A = B，我们实际上就可以把p移到p'的位置，再从箭头位置开始比较。

也就是说，如果模式串p在 i 位置发生了不匹配，我们知道它的[0 ~ i - 1]部分的相同的前缀A和后缀B，那么就可以对模式串p进行移动。

注：这里若有多组相同的A和B，应该取最长的那一组。

预处理

预处理就是在开始匹配前，把模式串中每个位置 i 对应的的最长的A = B的长度求出，也就是next数组。

这里的预处理用到了动态规划的思想：

假设现在已经计算了前 i 个next，计算i + 1时，有两种情况：

情况1

这里A和B为 next[i] 部分的最长的相同前后缀，如果i + 1位置的字符和A后面的一个字符相同，那么就有next[i + 1] = next[i] + 1。

情况2

如果不同：

 那么next[i + 1]一定比next[i]小(可反证)，设i + 1的相同前后缀 = C部分 + O：

注意到A = B，所以C是B的后缀，所以也是A的后缀，那么C也就是A的相同前后缀， 只要比较C后面的字符是否是O即可，如果不同，则继续递归的寻找下去。

代码如下：

/*
 * next记录的是长度
 */
void GetNext(const string& p, vector& next) {
  next[0] = 0;
  int k = 0;
  for (int i = 1; i < p.size(); ++i) {
    while (k > 0 && p[k] != p[i]) {
      k = next[k - 1];
    }
    if (p[k] == p[i]) {
      ++k;
    }
    next[i] = k;
  }
}

搜索

bool KMPSearch(const string& s, const string& p) {
  vector next(p.size());
  GetNext(p, next);
  int i = 0, j = 0;
  while (i != s.size() && j != p.size()) {
    if (s[i] == p[j]) {
      ++i;
      ++j;
    } else {
      if (j == 0) {
        ++i;
      } else {
        /* j位置不匹配，根据next[j - 1]进行移动 */
        j = next[j - 1];
      }
    }
  }
  return j == p.size();
}