

Z 函数（扩展 KMP）

假设我们有一个长度为的字符串。该字符串的 Z 函数 为一个长度为的数组，其中第个元素为满足从位置开始且为前缀的字符串的最大长度。

换句话说，是和从开始的的后缀的最大公共前缀长度。

注意：为了避免歧义，在这篇文章中下标从开始，即的第一个字符下标为，最后一个字符下标为。

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 函数的高效算法¶

为了得到一个高效算法，我们将以到的顺序计算，但在计算一个新值的同时，我们将尝试尽最大努力使用之前已经计算好的值。

为了简便起见，定义 匹配段 为同一个前缀相同的那些子串。举例来说，所求 Z 函数的第个元素为从位置开始的匹配段的长度（其终止位置位于）。

为了达成目标，我们将始终保持 为最靠右的匹配段 。也就是说，在所有已探测到的匹配段中，我们将保持结尾最靠右的那一个。另一方面，下标可被认为是字符串已被算法扫描的边界；任何超过该点的字符都是未知的。

假设当前下标为（即我们要计算的下一个 Z 函数值的下标），则有两种情况：

-- 当前位置在我们已处理位置之外。

我们接下来使用 朴素算法 （即一个一个的比较字符）来计算。注意如果最后，我们需要更新最靠右的匹配段的下标，因为新的一定比之前的优。
-- 当前位置位于当前匹配段之内。

那么我们可以用已计算过的 Z 函数值来“初始化” 至某值（至少比“从零开始”要好），甚至可能是某些较大的值。

为了做到这一点，我们注意到子串和匹配。这意味着作为的一个初始近似，我们可以直接使用对应于段的已计算过的 Z 函数值，也即。

然而，可能太大了：将其应用到位置结果可能超过下标。这种做法并不合法，原因在于我们对右侧的字符一无所知：他们可能并不满足要求。

此处给出一个相似场景的例子：

当我们尝试计算末尾位置（）的值时，当前匹配的段为。位置会匹配位置，其 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] = min(r - i + 1, z[i - l]);
    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;
}

对该实现的注释¶

整个解法被作为一个函数给出。该函数返回一个长度为的数组 -- 的 Z 函数。

数组被初始化为全。当前最右的匹配段被假定为（一个故意为之的不包含任何的小段）。

在循环内，对于，我们首先确定的初始值 -- 其要么保持为或者使用前述公式计算。

之后，朴素算法尝试尽可能多的增加值。

最后，如果必要（即如果），我们更新最右匹配段。

算法的渐进行为¶

我们将证明上述算法的运行时间关于字符串长度呈线性 -- 即其时间复杂度为。

该证明十分简单。

我们只关心内层 while 循环，因为其余部分在一次循环中只是一堆常数次操作，其时间复杂度总和为。

我们将证明 while 的 每次迭代 都将增加匹配段的右边界。

为了做到这一点，我们将考虑算法的所有分支：

在这种情况下，要么 while 循环不进行任何迭代（如果），要么其将从位置开始进行若干次迭代，其中每次迭代将向右移动一个字符。每次迭代后，右边界必定被更新。

因此我们证明了，当时， while 循环的每轮迭代都会使新的增加。
在这种情况下，我们将初始化为由前述公式给出的某个具体。将和比较，可能有三种情况：
- 我们证明在这种情况下 while 循环不会进行任何迭代。
  
  这是十分容易证明的，比如通过反证法：如果 while 循环进行了至少一次迭代，这意味着初始近似是不准确的（小于匹配的实际长度）。但是由于和是一样的，这推出的值是错误的（比其该有的值小）。
  
  所以，因为是正确的且其值小于，故该值同所求的是相同的。
- 在这种情况下， while 循环可能会进行若干次迭代。因为我们从开始比较，而其位置已经超过了区间，故每次迭代都会使增加。
- 根据的定义，这种情况是不可能的。

综上，我们已经证明了内层循环的每次迭代都会使向右移动。由于不可能超过，这意味着内层循环至多进行轮迭代。

因为该算法的剩余部分显然时间复杂度为，所以我们已经证明了计算 Z 函数的整个算法时间复杂度为线性。

应用¶

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

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

查找子串¶

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

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

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

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

一个字符串中本质不同子串的数目¶

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

我们将迭代的解决该问题。也即：在知道了当前的本质不同子串的数目的情况下，在末尾添加一个字符后重新计算该数目。

令为当前的本质不同子串数量。我们添加一个新的字符至。显然，会有一些新的子串以新的字符结尾（换句话说，那些以该字符结尾且我们之前未曾遇到的子串）。

构造字符串并将其反转（以相反顺序书写其字符）。我们现在的任务是计算有多少的前缀未在的其余任何地方出现。让我们计算的 Z 函数并找到其最大值。显然，的长度为的前缀出现在中间的某个位置。自然的，更短的前缀也出现了。

所以，我们已经找到了当将字符添加至后新出现的子串数目为。

作为其结果，该解法对于一个长度为的字符串的时间复杂度为。

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

字符串压缩¶

给定一个长度为的字符串，找到其最短的“压缩”表示，即：寻找一个最短的字符串，使得可以被的一份或多份拷贝的拼接表示。

其中一种解法为：计算的 Z 函数，从小到大循环所有满足整除的。在找到第一个满足的时终止。那么该字符串可被压缩为长度的字符串。

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

练习题目¶

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

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