Z 函数(扩展 KMP)

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

定义

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

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

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

解释

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

朴素算法

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

实现
1
2
3
4
5
6
7
8
// C++ Version
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;
}
1
2
3
4
5
6
7
8
# Python Version
def z_function_trivial(s):
    n = len(s)
    z = [0] * n
    for i in range(1, n):
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
    return z

线性算法

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

在该算法中,我们从 顺次计算 的值()。在计算 的过程中,我们会利用已经计算好的

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

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

在计算 的过程中:

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

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

实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// C++ Version
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;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
# Python Version
def z_function(s):
    n = len(s)
    z = [0] * n
    l, r = 0, 0
    for i in range(1, n):
        if i <= r and z[i - l] < r - i + 1:
            z[i] = z[i - l]
        else:
            z[i] = max(0, r - i + 1)
            while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                z[i] += 1
        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。