

Z 函数（扩展 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。

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：LeoJacob, Marcythm, minghu6
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用