

Z Function (Ex. KMP)

约定：字符串下标以为起点。

对于个长度为的字符串。定义函数表示和（即以开头的后缀）的最长公共前缀（LCP）的长度。被称为的 Z 函数。特别地，。

国外一般将计算该数组的算法称为 Z Algorithm，而国内则称其为 扩展 KMP。

这篇文章介绍在时间复杂度内计算 Z 函数的算法以及其各种应用。

样例¶

下面若干样例展示了对于不同字符串的 Z 函数：

朴素算法¶

Z 函数的朴素算法复杂度为：

vector<int> z_function_trivial(string s) {
  int n = (int)s.length();
  vector<int> z(n);
  for (int i = 1; i < n; ++i)
    while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
  return z;
}

线性算法¶

如同大多数字符串主题所介绍的算法，其关键在于，运用自动机的思想寻找限制条件下的状态转移函数，使得可以借助之前的状态来加速计算新的状态。

在该算法中，我们从到顺次计算的值（）。在计算的过程中，我们会利用已经计算好的。

对于，我们称区间是的 匹配段，也可以叫 Z-box。

算法的过程中我们维护右端点最靠右的匹配段。为了方便，记作。根据定义，是的前缀。在计算时我们保证。初始时。

在计算的过程中：

如果，那么根据的定义有，因此。这时：
- 若，则。
- 否则，这时我们令，然后暴力枚举下一个字符扩展直到不能扩展为止。
如果，那么我们直接按照朴素算法，从开始比较，暴力求出。
在求出后，如果，我们就需要更新，即令。

可以访问这个网站来看 Z 函数的模拟过程。

实现¶

vector<int> z_function(string s) {
  int n = (int)s.length();
  vector<int> z(n);
  for (int i = 1, l = 0, r = 0; i < n; ++i) {
    if (i <= r && z[i - l] < r - i + 1) {
      z[i] = z[i - l];
    } else {
      z[i] = max(0, r - i + 1);
      while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
    }
    if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
  }
  return z;
}

复杂度分析¶

对于内层 while 循环，每次执行都会使得向后移至少位，而，所以总共只会执行次。

对于外层循环，只有一遍线性遍历。

总复杂度为。

应用¶

我们现在来考虑在若干具体情况下 Z 函数的应用。

这些应用在很大程度上同前缀函数的应用类似。

匹配所有子串¶

为了避免混淆，我们将称作文本，将称作模式。所给出的问题是：寻找在文本中模式的所有出现（occurrence）。

为了解决该问题，我们构造一个新的字符串，也即我们将和连接在一起，但是在中间放置了一个分割字符（我们将如此选取使得其必定不出现在和中）。

首先计算的 Z 函数。接下来，对于在区间中的任意，我们考虑以为开头的后缀在中的 Z 函数值。如果，那么我们知道有一个的出现位于的第个位置，否则没有的出现位于的第个位置。

其时间复杂度（同时也是其空间复杂度）为。

本质不同子串数¶

给定一个长度为的字符串，计算的本质不同子串的数目。

考虑计算增量，即在知道当前的本质不同子串数的情况下，计算出在末尾添加一个字符后的本质不同子串数。

令为当前的本质不同子串数。我们添加一个新的字符至的末尾。显然，会出现一些以结尾的新的子串（以结尾且之前未出现过的子串）。

设串是的反串（反串指将原字符串的字符倒序排列形成的字符串）。我们的任务是计算有多少的前缀未在的其他地方出现。考虑计算的 Z 函数并找到其最大值。则的长度小于等于的前缀的反串在中是已经出现过的以结尾的子串。

所以，将字符添加至后新出现的子串数目为。

算法时间复杂度为。

值得注意的是，我们可以用同样的方法在时间内，重新计算在端点处添加一个字符或者删除一个字符（从尾或者头）后的本质不同子串数目。

字符串整周期¶

给定一个长度为的字符串，找到其最短的整周期，即寻找一个最短的字符串，使得可以被若干个拼接而成的字符串表示。

考虑计算的 Z 函数，则其整周期的长度为最小的的因数，满足。

该事实的证明同应用前缀函数的证明一样。

练习题目¶

本页面主要译自博文 Z-функция строки и её вычисление 与其英文翻译版 Z-function and its calculation。其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0。

Last update and/or translate time of this article，Check the history
Found smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
Contributor of this article LeoJacob, Marcythm, minghu6
Translator of this article Visit the original article!
The article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.