KMP

KMP 算法是一种字符串匹配算法，可以在 $O(n+m)$ 的时间复杂度内实现两个字符串的匹配。这个算法由高德纳和沃恩·普拉特在1974年构思，同年詹姆斯·H·莫里斯也独立地设计出该算法，最终三人于1977年联合发表。Knuth-Morris-Pratt （简称为KMP算法）

• 尽可能利用残余的信息，是KMP算法的思想所在；
• 如果把模式串视为一把标尺，在主串上移动，Brute-Force 就是每次失配之后只右移一位；KMP 算法则是每次失配之后，移很多位，跳过那些不可能匹配成功的位置。

前缀函数

KMP 算法是对前缀函数的一种应用。对前缀函数的定义：

给定一个长度为 $n$ 的字符串 $s$，其 前缀函数 被定义为一个长度为 $n$ 的数组 $\pi$。 其中 $\pi [i]$ 的定义是：

1. 如果子串 $s[0\dots i]$ 有一对相等的真前缀与真后缀：$s[0\dots k-1]$ 和 $s[i-(k-1)\dots i]$，那么 $\pi [i]$ 就是这个相等的真前缀（或者真后缀，因为它们相等：)）的长度，也就是 $\pi [i]=k$；
2. 如果不止有一对相等的，那么 $\pi [i]$ 就是其中最长的那一对的长度；
3. 如果没有相等的，那么 $\pi [i]=0$。

简单来说 $\pi [i]$ 就是，子串 $s[0\dots i]$ 最长的相等的真前缀与真后缀的长度。

用数学语言描述如下：

$$\pi [i]=\underset{k=0\dots i}{max}\{k:s[0\dots k-1]=s[i-(k-1)\dots i]\}$$

特别地，规定 $\pi [0]=0$。

朴素的暴力运算实现

1. 在一个循环中以 $i=1\to n-1$ 的顺序计算前缀函数 $\pi [i]$ 的值（$\pi [0]$ 被赋值为 $0$）；
2. 为了计算当前的前缀函数值 $\pi [i]$，我们令变量 $j$ 从最大的真前缀长度 $i$ 开始尝试；
3. 如果当前长度下真前缀和真后缀相等，则此时长度为 $\pi [i]$，否则令 j 自减 1，继续匹配，直到 $j=0$；
4. 如果 $j=0$ 并且仍没有任何一次匹配，则置 $\pi [i]=0$ 并移至下一个下标 $i+1$。

vector<int> prefix_function(string s) {
  int n = s.length();
  vector<int> pi(n);
  for (int i = 1; i < n; i++) {
    for (int j = i; j >= 0; j--) {
      // j 为前后缀的长度，从大到小尝试
      if (s.substr(0, j) == s.substr(i - j + 1, j)) {
        pi[i] = j;
        break;
      }
    }
  }
  return pi;
}

使用动态规划优化的实现

优化的要点：

• 相邻的前缀函数值至多增加 1（在最好的情况下增加 1）；
• 下一个前缀函数值要么增加 1，要么维持不变，要么减少；

前缀函数与 KMP 算法 - OI Wiki (oi-wiki.org) KMP算法 - 维基百科，自由的百科全书 (wikipedia.org) The Knuth-Morris-Pratt Algorithm in my own words - jBoxer (jakeboxer.com)