KMP

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

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

前缀函数¶

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

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

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

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

用数学语言描述如下：

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

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

朴素的暴力运算实现¶

在一个循环中以 \(i = 1\to n - 1\) 的顺序计算前缀函数 \(\pi[i]\) 的值（\(\pi[0]\) 被赋值为 \(0\)）；
为了计算当前的前缀函数值 \(\pi[i]\)，我们令变量 \(j\) 从最大的真前缀长度 \(i\) 开始尝试；
如果当前长度下真前缀和真后缀相等，则此时长度为 \(\pi[i]\)，否则令 j 自减 1，继续匹配，直到 \(j=0\)；
如果 \(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)