23. 前缀函数与 KMP 算法

23.1. 字符串基础

子串

字符串 \(S\) 的子串 \(S[i:j],\ i \leq j\) ，表示 \(S\) 串中从 \(i\) 到 \(j\) 这一段（注意，这里表示为双闭区间），也就是顺次排列 \(S[i],S[i+1],\cdots,S[j]\) 形成的字符串，子串长度为 \(j-i+1\) 。

有时也会用 \(S[i:j],\ i > j\) 来表示空串。

子序列

字符串 \(S\) 的子序列是从 \(S\) 中将若干元素提取出来且不改变相对位置形成的序列，即 \(S[p_1],S[p_2],\cdots,S[p_k]\) ， \(0\le p_1 < p_2 < \cdots < p_k < |S|\) 。

前缀

前缀是指从串首开始到某个位置 \(i\) 结束的一个特殊子串。字符串 \(S\) 以 \(S[i]\) 结尾的前缀表示为 \(\mathrm{prefix}(S,i) = S[0:i]\) 。

真前缀 指除了 \(S\) 本身之外的前缀。

举例来说，字符串 \(abcabcd\) 的所有前缀为 \(\{ a, ab, abc, abca, abcab, abcabc, abcabcd \}\) ，而它的真前缀为 \(\{ a, ab, abc, abca, abcab, abcabc \}\) 。

后缀

后缀是指从某个位置 \(i\) 开始到整个串末尾结束的一个特殊子串。字符串 \(S\) 以 \(S[i]\) 开头的后缀表示为 \(\mathrm{suffix}(S,i) = S[i:|S|-1]\) 。

真后缀 指除了 \(S\) 本身之外的前缀。

举例来说，字符串 \(abcabcd\) 的所有后缀为 \(\{ d, cd, bcd, abcd, cabcd, bcabcd, abcabcd \}\) ，而它的真后缀为 \(\{ d, cd, bcd, abcd, cabcd, bcabcd \}\) 。

字典序

以第 \(i\) 个字符作为第 \(i\) 关键字进行大小比较，空字符小于字符集内任何字符（即： \(a < aa\) ）。

23.2. 前缀函数

给定一个长度为 \(n\) 的字符串 \(S\) ，其前缀函数被定义为一个长度为 \(n\) 的数组 \(\pi\) ：

如果子串 \(S[0:i]\) 有一对相等的真前缀与真后缀：\(S[0:k-1]\) 和 \(S[i-(k-1):i]\) ，那么 \(\pi[i]\) 就是这个相等的真前缀/真后缀的长度，即 \(\pi[i] = k\) ；
如果不止有一对相等的真前缀与真后缀，那么 \(\pi[i]\) 就是其中最长的那一对的长度；
如果没有相等的，那么 \(\pi[i] = 0\) 。

简单来说， \(\pi[i]\) 就是子串 \(S[0:i]\) 最长的相等的真前缀与真后缀的长度。特别地，规定 \(\pi[0] = 0\) 。

举例来说，对于字符串 \(abcabcd\) ：

\(\pi[0]=0\) ，因为 \(a\) 没有真前缀和真后缀，根据规定为 0。
\(\pi[1]=0\) ，因为 \(ab\) 无相等的真前缀和真后缀。
\(\pi[2]=0\) ，因为 \(abc\) 无相等的真前缀和真后缀。
\(\pi[3]=1\) ，因为 \(abca\) 只有一对相等的真前缀和真后缀：\(a\)，长度为 1。
\(\pi[4]=2\) ，因为 \(abcab\) 相等的真前缀和真后缀只有 \(ab\)，长度为 2。
\(\pi[5]=3\) ，因为 \(abcabc\) 相等的真前缀和真后缀只有 \(abc\)，长度为 3。
\(\pi[6]=0\) ，因为 \(abcabcd\) 无相等的真前缀和真后缀。

同理可以计算字符串 \(aabaaab\) 的前缀函数为 \([0, 1, 0, 1, 2, 2, 3]\) 。

23.3. 朴素算法

两重循环、子串比较，时间复杂度 \(\mathcal{O}(n^3)\) 。

vector<int> prefixFunction(const string& s)
{
  int n = (int)s.length();
  vector<int> pi(n); // pi[0] = 0
  for (int i = 1; i < n; i++)
    for (int j = i; j >= 0; j--)
      if (s.substr(0, j) == s.substr(i - j + 1, j))
      {
        pi[i] = j;
        break;
      }
  return pi;
}

23.4. 优化算法

第一个优化

相邻的前缀函数值至多增加 1，即 \(\pi[i+1] - \pi[i] \leq 1\) 。

当 \(S[i+1] = S[\pi[i]]\) ，此时 \(\pi[i+1] = \pi[i] + 1\) 。

\[\underbrace{\overbrace{S_0 ~ S_1 ~ S_2}^{\pi[i] = 3} ~ S_3}_{\pi[i+1] = 4} ~ \cdots ~ \underbrace{\overbrace{S_{i-2} ~ S_{i-1} ~ S_{i}}^{\pi[i] = 3} ~ S_{i+1}}_{\pi[i+1] = 4}\]

第二个优化

当 \(S[i+1] \neq S[\pi[i]]\) ，我们希望找到对于子串 \(S[0:i]\) ，仅次于 \(\pi[i]\) 的第二长度 \(j\) ，使得在位置 \(i\) 的前缀性质仍得以保持，也即 \(S[0:j - 1] = S[i - j + 1: i]\) 。

\[\overbrace{\underbrace{S_0 ~ S_1}_j ~ S_2 ~ S_3}^{\pi[i]} ~ \cdots ~ \overbrace{S_{i-3} ~ S_{i-2} ~ \underbrace{S_{i-1} ~ S_{i}}_j}^{\pi[i]} ~ S_{i+1}\]

如果我们找到了这样的长度 \(j\) ，那么仅需要再次比较 \(S[i+1]\) 和 \(S[j]\) 。如果它们相等，那么就有 \(\pi[i + 1] = j + 1\) ；否则，我们需要找到子串 \(S[0:i]\) 中仅次于 \(j\) 的第二长度 \(j^{(2)}\) ，使得前缀性质得以保持，如此反复，直到 \(j=0\) 。如果 \(S[i+1] \neq S[0]\) ，则 \(\pi[i + 1] = 0\) 。

观察上图可以发现，因为 \(S[0:\pi[i] - 1] = S[i- \pi[i] + 1: i]\) ，所以对于 \(S[0:i]\) 的第二长度 \(j\) ，有这样的性质：

\[S[0:j - 1] = S[i - j + 1: i]= S[\pi[i] - j : \pi[i] - 1].\]

也就是说 \(j=\pi[\pi[i] - 1]\) 。

显然我们可以得到一个关于 \(j\) 的状态转移方程：

\[j^{(n)}=\pi[j^{(n-1)} - 1], \ j^{(n-1)} > 0.\]

所以最终我们可以构建一个不需要进行任何字符串比较，并且只进行 \(\mathcal{O}(n)\) 次操作的算法。

vector<int> prefixFunction(const string& s)
{
  int n = (int)s.length();
  vector<int> pi(n);
  for (int i = 1; i < n; i++)
  {
    int j = pi[i - 1];
    while (j > 0 && s[i] != s[j]) j = pi[j - 1];
    if (s[i] == s[j]) j++;
    pi[i] = j;
  }
  return pi;
}

虽然上面代码中还有一个 while 循环，但是该过程的摊还代价是 \(\mathcal{O}(1)\) ，当前面的 while 循环执行得比较长时，后续的 while 循环会更短。

这是一个在线算法，即当数据到达时处理它。举例来说，可以一个字符一个字符的读取字符串，立即处理它们以计算出每个字符的前缀函数值。该算法仍然需要存储字符串本身以及先前计算过的前缀函数值，但如果我们已经预先知道该字符串前缀函数的最大可能取值 \(M\) ，那么我们仅需要存储该字符串的前 \(M+1\) 个字符以及对应的前缀函数值（ \(+1\) 表示存储前一个位置的前缀函数值 \(\pi[i - 1]\) ；while 循环中 \(\pi[j - 1] < M\) ）。

23.5. 查找子串：KMP 算法

问题描述

给定一个文本 \(T\) 和一个字符串 \(S\) ，我们尝试找到并展示 \(S\) 在 \(T\) 中的所有出现位置（Occurrence）。

KMP 算法

设 \(S\) 长度为 \(n\) ， \(T\) 长度为 \(m\) 。

构造一个字符串 \(S\#T\) ，长度为 \(m+n+1\) ，其中 \(\#\) 是一个既不出现在 \(S\) 中也不出现在 \(T\) 中的分隔符。接下来计算该字符串的前缀函数。现在考虑该前缀函数除去开头 \(n+1\) 个值（即属于字符串 \(S\) 和分隔符的函数值）后其余函数值的意义。根据定义，\(\pi[i]\) 为右端点在 \(i\) 处的前缀函数值，由于分隔符的存在，该长度不可能超过 \(n\) 。而如果等式 \(\pi[i] = n\) 成立，则意味着 \(S\) 完整地出现在该位置（即 \(S\) 右端点与位置 \(i\) 对齐）。注意：该位置的下标 \(i\) 是对字符串 \(S\#T\) 而言的，当 \(\pi[i] = n\) 成立，则字符串 \(S\) 在字符串 \(T\) 的 \(i - (n + 1) - (n - 1) = i - 2n\) 处出现。

正如在前缀函数的计算中已经提到的那样，如果我们知道前缀函数的值永远不超过一特定值，那么我们不需要存储整个字符串以及整个前缀函数，而只需要二者开头的一部分。由于 \(\pi[i] \leq n\) ，这意味着只需要存储字符串 \(S\#\) 以及相应的前缀函数值即可。我们可以一次读入字符串 \(T\) 的一个字符并计算当前位置的前缀函数值。

因此 Knuth-Morris-Pratt 算法（简称 KMP 算法）用 \(\mathcal{O}(m+n)\) 的时间以及 \(\mathcal{O}(n)\) 的空间解决了该问题。

23.6. 参考资料

字符串基础

https://oi-wiki.org/string/basic/

前缀函数与 KMP 算法

https://oi-wiki.org/string/kmp/#knuth-morris-pratt