跳转至

Z 函数(扩展 KMP)

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

换句话说, z[i] s 和从 i 开始的 s 的后缀的最大公共前缀长度。

注意:为了避免歧义,在这篇文章中下标从 0 开始,即 s 的第一个字符下标为 0 ,最后一个字符下标为 n - 1

Z 函数的第一个元素, z[0] ,通常不是良定义的。在这篇文章中我们假定它是 0 (虽然在算法实现中这没有任何影响)。

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

这篇文章包含在 O(n) 时间复杂度内计算 Z 函数的算法以及其各种应用。

样例

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

  • Z(\mathtt{aaaaa}) = [0, 4, 3, 2, 1]
  • Z(\mathtt{aaabaab}) = [0, 2, 1, 0, 2, 1, 0]
  • Z(\mathtt{abacaba}) = [0, 0, 1, 0, 3, 0, 1]

朴素算法

Z 函数的形式化定义可被表述为下列基础的 O(n^2) 实现。

1
2
3
4
5
6
7
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;
}

我们做的仅仅为循环每个位置 i ,并通过下述做法更新每个 z[i] :从 z[i] = 0 开始,只要我们没有失配(并且没有到达末尾)就将其加 1

诚然,这并不是一个高效的实现。我们接下来将展示一个高效实现的构造过程。

计算 Z 函数的高效算法

为了得到一个高效算法,我们将以 i = 1 n - 1 的顺序计算 z[i] ,但在计算一个新值的同时,我们将尝试尽最大努力使用之前已经计算好的值。

为了简便起见,定义匹配段为同 s 一个前缀相同的那些子串。举例来说,所求 Z 函数的第 i 个元素 z[i] 为从位置 i 开始的匹配段的长度(其终止位置位于 i + z[i] - 1 )。

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

假设当前下标为 i (即我们要计算的下一个 Z 函数值的下标),则有两种情况:

  • i > r -- 当前位置在我们已处理位置之外

    我们接下来使用朴素算法(即一个一个的比较字符)来计算 z[i] 。注意如果最后 z[i] > 0 ,我们需要更新最靠右的匹配段的下标,因为新的 r = i + z[i] - 1 一定比之前的 r 优。

  • i \le r -- 当前位置位于当前匹配段 [l;r] 之内。

    那么我们可以用已计算过的 Z 函数值来 “初始化” z[i] 至某值(至少比 “从零开始” 要好),甚至可能是某些较大的值。

    为了做到这一点,我们注意到子串 s[l\dots r] s[0 \dots r - l] 匹配。这意味着作为 z[i] 的一个初始近似,我们可以直接使用对应于段 s[0 \dots r - l] 的已计算过的 Z 函数值,也即 z[i - l]

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

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

    s=\mathtt{aaaabaa}

    当我们尝试计算末尾位置( i = 6 )的值时,当前匹配的段为 [5;6] 。位置 6 会匹配位置 6 - 5 = 1 ,其 Z 函数值为 z[1] = 3 。显然,我们不能将 z[6] 初始化为 3 ,因为这完全不对。我们可以初始化的最大值为 1 -- 因为这是使我们不超过段 [l;r] 的边界 r 的最大可能取值。

    因此,我们可以放心的将下列值作为 z[i] 的一个初始近似:

    z_0[i] = \min(r - i + 1, z[i - l])

    当将 z[i] 初始化为 z_0[i] 后,我们尝试使用朴素算法增加 z[i] 的值 -- 因为宏观来讲,对于边界 r 之后的事情,我们无法得知段是否会继续匹配还是失配。

综上所述,整个算法被划分成两种情况,他们只在设置 z[i] 初始值时有所不同:在第一种情况下,其被认为为 0 ,在第二种情况下它由先前已计算过的值确定(使用前述公式)。之后,该算法的两个分支都被规约为实现朴素算法。当我们设置完初始值后,该算法即开始执行。

该算法看起来非常简单。尽管在每轮迭代都会运行朴素算法,但我们已经取得了巨大进步:获得了一个时间复杂度为线性的算法。之后我们会证明这一点。

实现

实现相对来说十分简明:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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;
}

对该实现的注释

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

数组 z 被初始化为全 0 。当前最右的匹配段被假定为 [0;0] (一个故意为之的不包含任何 i 的小段)。

在循环内,对于 i=1\dots n - 1 ,我们首先确定 z[i] 的初始值 -- 其要么保持为 0 或者使用前述公式计算。

之后,朴素算法尝试尽可能多的增加 z[i] 值。

最后,如果必要(即如果 i + z[i] - 1 > r ),我们更新最右匹配段 [l;r]

算法的渐进行为

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

该证明十分简单。

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

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

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

  • i > r

    在这种情况下,要么 while 循环不进行任何迭代(如果 s[0] \neq s[i] ),要么其将从位置 i 开始进行若干次迭代,其中每次迭代将向右移动一个字符。每次迭代后,右边界 r 必定被更新。

    因此我们证明了,当 i > r 时,while 循环的每轮迭代都会使新的 r 增加 1

  • i \le r

    在这种情况下,我们将 z[i] 初始化为由前述公式给出的某个具体 z_0 。将 z_0 r - i + 1 比较,可能有三种情况:

    • z_0 < r - i + 1

      我们证明在这种情况下 while 循环不会进行任何迭代。

      这是十分容易证明的,比如通过反证法:如果 while 循环进行了至少一次迭代,这意味着初始近似 z[i] = z_0 是不准确的(小于匹配的实际长度)。但是由于 s[l\dots r] s[0\dots r - l] 是一样的,这推出 z[i - l] 的值是错误的(比其该有的值小)。

      所以,因为 z[i - l] 是正确的且其值小于 r - i + 1 ,故该值同所求的 z[i] 是相同的。

    • z_0 = r - i + 1

      在这种情况下,while 循环可能会进行若干次迭代。因为我们从 s[r + 1] 开始比较,而其位置已经超过了区间 [l;r] ,故每次迭代都会使 r 增加。

    • z_0 > r - i + 1

      根据 z_0 的定义,这种情况是不可能的。

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

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

应用

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

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

查找子串

为了避免混淆,我们将 t 称作文本,将 p 称作模式。所给出的问题是:寻找在文本 t 中模式 p 的所有出现(occurrence)。

为了解决该问题,我们构造一个新的字符串 s = p + \diamond + t ,也即我们将 p t 连接在一起,但是在中间放置了一个分割字符 \diamond (我们将如此选取 \diamond 使得其必定不出现在 p t 中)。

首先计算 s 的 Z 函数。接下来,对于在区间 [0; \operatorname{length}(t) - 1] 中的任意 i ,我们考虑其对应的值 k = z[i + \operatorname{length}(p) + 1] 。如果 k 等于 \operatorname{length}(p) ,那么我们知道有一个 p 的出现位于 t 的第 i 个位置,否则没有 p 的出现位于 t 的第 i 个位置。

其时间复杂度(同时也是其空间复杂度)为 O(\operatorname{length}(t) + \operatorname{length}(p))

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

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

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

k 为当前 s 的本质不同子串数量。我们添加一个新的字符 c s 。显然,会有一些新的子串以新的字符 c 结尾(换句话说,那些以该字符结尾且我们之前未曾遇到的子串)。

构造字符串 t = s + c 并将其反转(以相反顺序书写其字符)。我们现在的任务是计算有多少 t 的前缀未在 t 的其余任何地方出现。让我们计算 t 的 Z 函数并找到其最大值 z_{\max} 。显然, t 的长度为 z_{\max} 的前缀出现在 t 中间的某个位置。自然的,更短的前缀也出现了。

所以,我们已经找到了当将字符 c 添加至 s 后新出现的子串数目为 \operatorname{length}(t) - z_{\max}

作为其结果,该解法对于一个长度为 n 的字符串的时间复杂度为 O(n^2)

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

字符串压缩

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

其中一种解法为:计算 s 的 Z 函数,从小到大循环所有满足 i 整除 n i 。在找到第一个满足 i + z[i] = n i 时终止。那么该字符串 s 可被压缩为长度 i 的字符串。

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

练习题目


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


评论