企业官网建设流程全解析

OI-wiki 字符串专题：Z 函数（扩展 KMP）算法详解与 O(n) 实现

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

本文是 OI-wiki 字符串专题中关于Z 函数（国内竞赛圈习称扩展 KMP / exKMP）的技术指南。Z 函数用一个长度为 $n$ 的数组记录字符串每个后缀与自身前缀的最长公共前缀（LCP）长度，它既是一类基础字符串预处理工具，也是 前缀函数（KMP） 的姊妹算法，被广泛应用于子串匹配、本质不同子串统计、字符串整周期判定等场景。读完本文，你将掌握 Z 函数的数学定义、朴素算法、基于 Z-box 的 $O(n)$ 线性算法及其证明，并能够直接运行仓库文档中给出的 C++ / Python 实现解决实际问题。

定义

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

对于一个长度为 $n$ 的字符串 $s$，定义函数 $z[i]$ 表示 $s$ 和 $s[i,n-1]$（即以 $s[i]$ 开头的后缀）的最长公共前缀（LCP）的长度，则 $z$ 被称为 $s$ 的Z 函数。特别地，规定 $z[0] = 0$。

术语说明：国外一般将计算该数组的算法称为Z Algorithm，而国内则称其为扩展 KMP（exKMP）。两者指向的是同一套概念与算法，只是命名习惯不同。

直观样例

下面若干样例展示了对于不同字符串的 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[1]=4$ 表示后缀aaaa与前缀aaaaa的最长公共前缀长度为 $4$；$z[4]=1$ 表示后缀a与前缀的 LCP 为 $1$，依此类推。可以注意到，$z[i]$ 的值永远不会超过 $n - i$，因为后缀本身就只有 $n-i$ 个字符。

朴素算法

最直接的思路就是按定义逐位暴力比较：对每个 $i$，从 $s[i]$ 开始与 $s[0]$ 对齐，逐字符向后比对，直到失配或到达串尾。这样每个位置 $i$ 最坏要比较 $O(n-i)$ 次，总复杂度为 $O(n^2)$。

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; }

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

这里while循环中的下标写法值得注意：s[z[i]]是当前要比较的“前缀侧”字符，s[i + z[i]]是“后缀侧”字符，两者相等则z[i]自增。对形如aaaa...a的全同字符输入，该朴素实现的比较次数约为 $\frac{n^2}{2}$，需要线性算法来优化。

线性算法

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

在该算法中，我们从 $1$ 到 $n-1$ 顺次计算 $z[i]$ 的值（$z[0]=0$）。在计算 $z[i]$ 的过程中，我们会利用已经计算好的 $z[0],\ldots,z[i-1]$。

Z-box 核心思想

对于 $i$，我们称区间 $[i,i+z[i]-1]$ 是 $i$ 的匹配段，也可以叫 Z-box（Z 盒子）。

算法的过程中我们维护右端点最靠右的匹配段，记作 $[l,r]$。根据定义，$s[l,r]$ 是 $s$ 的前缀。在计算 $z[i]$ 时我们保证 $l\le i$。初始时 $l=r=0$。

在计算 $z[i]$ 的过程中，分两种情况讨论：

1. 如果 $i\le r$：根据 $[l,r]$ 的定义有 $s[i,r] = s[i-l,r-l]$，也就是说位置 $i$ 处的后缀与位置 $i-l$ 处的后缀共享同样的前缀匹配关系，因此 $z[i]\ge \min(z[i-l],r-i+1)$。这时：
   • 若 $z[i-l] < r-i+1$，说明从前缀侧复制的匹配长度不会撞到 Z-box 右边界，直接令 $z[i] = z[i-l]$；
   • 否则 $z[i-l]\ge r-i+1$，这时令 $z[i] = r-i+1$，然后暴力枚举下一个字符扩展 $z[i]$，直到不能扩展为止。
2. 如果 $i>r$：当前位置已经不在任何已知匹配段内，没有可利用的历史信息，直接按照朴素算法，从 $s[i]$ 开始比较，暴力求出 $z[i]$。

在求出 $z[i]$ 后，如果 $i+z[i]-1>r$，说明当前匹配段右端比已维护的最右匹配段更远，需要更新 $[l,r]$，即令 $l=i,\ r=i+z[i]-1$。这一“右端点单调右移”的性质正是线性复杂度的来源。

实现

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; }

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

实现细节说明：

• z[i] = max(0, r - i + 1)：当 $i>r$ 时r - i + 1为负，需要取0，与朴素算法的“从 $s[i]$ 开始比较”语义一致；
• 分支条件z[i - l] < r - i + 1对应上文的“第一种情况中的第一种分支”，一旦不满足就进入可扩展分支；
• l与r的更新放在每轮末尾，保证下一轮迭代时维护的始终是最靠右的匹配段。

复杂度分析

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

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

因此总复杂度为 $O(n)$。这一“指针 $r$ 单调右移”的势能分析方式与 Manacher 算法 中维护最右回文边界的思想同源，OI-wiki 的 Manacher 页面 也明确指出"计算 Z 函数的算法和该算法较为类似，并同样具有线性时间复杂度"。

应用

我们现在来考虑在若干具体情况下 Z 函数的应用。这些应用在很大程度上同 前缀函数 的应用类似——两者都能在 $O(n)$ 时间内刻画字符串前缀与后缀的重叠关系，区别在于前缀函数 $\pi[i]$ 刻画的是"以 $i$ 结尾的最长相等真前后缀"，而 Z 函数 $z[i]$ 刻画的是"从 $i$ 开始的最长前缀匹配"。

匹配所有子串

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

为了解决该问题，我们构造一个新的字符串 $s = p + \diamond + t$，也即将 $p$ 和 $t$ 连接在一起，但在中间放置一个分割字符 $\diamond$（我们将如此选取 $\diamond$ 使得其必定不出现在 $p$ 和 $t$ 中，例如#、$等不在输入字符集中出现的字符）。

首先计算 $s$ 的 Z 函数。接下来，对于在区间 $[0,|t| - 1]$ 中的任意 $i$，我们考虑以 $t[i]$ 为开头的后缀在 $s$ 中的 Z 函数值 $k = z[i + |p| + 1]$。如果 $k = |p|$，那么我们知道有一个 $p$ 的出现位于 $t$ 的第 $i$ 个位置，否则没有 $p$ 的出现位于 $t$ 的第 $i$ 个位置。

这里的关键在于分隔符 $\diamond$：由于它不出现在 $p$ 与 $t$ 中，任何跨越分隔符的匹配都被强制终止，因此 $z$ 值被限制在 $|p|$ 以内，z[i + |p| + 1]恰好等于"从 $t[i]$ 开始能与 $p$ 的前缀匹配的最大长度"。当这个长度等于 $|p|$ 时即为一次完整匹配。

其时间复杂度（同时也是其空间复杂度）为 $O(|t| + |p|)$。这一构造方式与 KMP 页面 中用s + # + t计算前缀函数找子串的技巧完全同构，可以对照学习。

本质不同子串数

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

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

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

设串 $t$ 是 $s + c$ 的反串（反串指将原字符串的字符倒序排列形成的字符串）。我们的任务是计算有多少 $t$ 的前缀未在 $t$ 的其他地方出现。考虑计算 $t$ 的 Z 函数并找到其最大值 $z_{\max}$。则 $t$ 中长度小于等于 $z_{\max}$ 的前缀的反串在 $s$ 中是已经出现过的以 $c$ 结尾的子串——因为前缀在 $t$ 的某处再次出现，等价于其反串（即某个以 $c$ 结尾的子串）在 $s+c$ 中已经出现过。

所以，将字符 $c$ 添加至 $s$ 后新出现的子串数目为 $|t| - z_{\max}$。

算法时间复杂度为 $O(n^2)$：对每个增量步都要对当前串的反串重算一次 Z 函数。

值得注意的是，我们可以用同样的方法在 $O(n)$ 时间内，重新计算在端点处添加一个字符或者删除一个字符（从尾或者头）后的本质不同子串数目。这一增量维护技巧在动态维护子串信息的题目中非常实用。

字符串整周期

给定一个长度为 $n$ 的字符串 $s$，找到其最短的整周期，即寻找一个最短的字符串 $t$，使得 $s$ 可以被若干个 $t$ 拼接而成的字符串表示（如abcabcabc的最短整周期是abc，长度为 $3$）。

考虑计算 $s$ 的 Z 函数，则其整周期的长度为最小的 $n$ 的因数 $i$，满足 $i+z[i]=n$。

该事实的证明同应用 前缀函数 的证明一样：条件 $i+z[i]=n$ 意味着从位置 $i$ 开始的整个后缀都是前缀 $s[0,i-1]$ 的匹配，即长度为 $n-i$ 的前缀等于同长度的后缀，这等价于说 $s$ 有长度为 $n-i$ 的 border，进而 $i$ 是 $s$ 的一个周期；要求 $i$ 是 $n$ 的因数才能保证 $s$ 能被若干个完整块 $t=s[0,i-1]$ 恰好拼成。取满足条件的最小因数即为最短整周期；若不存在这样的因数，则答案就是 $n$ 本身（整周期为自身）。

仓库内关联与延伸阅读

Z 函数并非孤立的知识点，在 OI-wiki 的字符串专题中它与其他算法页面存在多处交叉引用：

• 前缀函数（KMP）：Z 函数最直接的姊妹算法，二者的应用场景（子串匹配、本质不同子串数、字符串压缩/周期）高度重叠，O(n) 实现思路互为镜像，强烈建议对照阅读；
• Manacher 算法：其维护最右回文边界的线性做法与 Z 函数的 Z-box 维护方式同构；
• Main–Lorentz 算法：在分析字符串的重复子串时，借助 Z 函数做到 $O(1)$ 计算某些关键的 LCP 匹配长度——例如通过计算 $\overline{u}$ 的 Z 函数求 $k_1$，通过计算 $v+#+u$ 的 Z 函数求 $k_2$（见 main-lorentz.md 中对 $k_1,k_2$ 的定义与计算方式）；
• 字符串基础：文中使用的前缀、后缀、子串等基础概念均出自该页面，可作为前置知识复习。

练习题目

以下练习覆盖了 Z 函数的定义理解、线性算法实现与三大经典应用，难度递进，可用于检验掌握程度（题目来源包括 Luogu、Codeforces、UVa、Codechef、LeetCode 等 OJ，可按题号自行检索）：

• Luogu P5410【模板】扩展 KMP/exKMP（Z 函数）——Z 函数的模板题，适合验证线性实现正确性；
• Luogu P7114【NOIP2020】字符串匹配——综合运用 Z 函数与计数技巧；
• CF126B Password——求既是前缀又是后缀且出现在中间的子串，Z 函数经典应用；
• UVa 455 Periodic Strings——字符串整周期判定，可直接套用"最小的 $n$ 的因数 $i$ 满足 $i+z[i]=n$"；
• UVa 11022 String Factoring——结合整周期思想的动态规划练习；
• UVa 11475 Extend to Palindrome——Z 函数在回文构造问题中的应用；
• Codechef Chef and Strings、Codeforces 432D Prefixes and Suffixes——Z 函数与计数统计的结合；
• Leetcode 2223 Sum of Scores of Built Strings——将 Z 函数应用到"分数求和"类统计问题。

小结

• Z 函数 $z[i]$ 记录后缀 $s[i..n-1]$ 与整串 $s$ 的最长公共前缀长度，$z[0]=0$；
• 朴素算法 $O(n^2)$ 按定义逐位比较，线性算法借助 Z-box $[l,r]$ 复用已计算的 $z$ 值，总复杂度 $O(n)$，且空间同样为 $O(n)$；
• 三大经典应用：分隔符拼接后 $O(|t|+|p|)$ 匹配所有子串；反串 + Z 最大值增量统计本质不同子串；条件 $i+z[i]=n$ 求最短整周期；
• 与 前缀函数、Manacher 互为姊妹/同类算法，可对照学习，并在 Main–Lorentz 等高级算法中作为 $O(1)$ 匹配查询的基础工具。

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki