Z 函数(扩展 KMP)约定:字符串下标以 00 为起点.
定义对于一个长度为 𝑛n 的字符串 𝑠s,定义函数 𝑧[𝑖]z[i] 表示 𝑠s 和 𝑠[𝑖,𝑛 −1]s[i,n−1](即以 𝑠[𝑖]s[i] 开头的后缀)的最长公共前缀(LCP)的长度,则 𝑧z 被称为 𝑠s 的 Z 函数.特别地,𝑧[0] =0z[0]=0.
国外一般将计算该数组的算法称为 Z Algorithm,而国内则称其为 扩展 KMP(exKMP).
这篇文章介绍在 𝑂(𝑛)O(n) 时间复杂度内计算 Z 函数的算法以及其各种应用.
解释下面若干样例展示了对于不同字符串的 Z 函数:
𝑧(𝚊𝚊𝚊𝚊𝚊) =[0,4,3,2,1]z(aaaaa)=[0,4,3,2,1]𝑧(𝚊𝚊𝚊𝚋𝚊𝚊𝚋) =[0,2,1,0,2,1,0]z(aaabaab)=[0,2,1,0,2,1,0]𝑧(𝚊𝚋𝚊𝚌𝚊𝚋𝚊) =[0,0,1,0,3,0,1]z(abacaba)=[0,0,1,0,3,0,1]朴素算法Z 函数的朴素算法复杂度为 𝑂(𝑛2)O(n2):
实现 C++Python1
2
3
4
5
6
7vector
int n = (int)s.length();
vector
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
7def 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
线性算法如同大多数字符串主题所介绍的算法,其关键在于,运用自动机的思想寻找限制条件下的状态转移函数,使得可以借助之前的状态来加速计算新的状态.
在该算法中,我们从 11 到 𝑛 −1n−1 顺次计算 𝑧[𝑖]z[i] 的值(𝑧[0] =0z[0]=0).在计算 𝑧[𝑖]z[i] 的过程中,我们会利用已经计算好的 𝑧[0],…,𝑧[𝑖 −1]z[0],…,z[i−1].
对于 𝑖i,我们称区间 [𝑖,𝑖 +𝑧[𝑖] −1][i,i+z[i]−1] 是 𝑖i 的 匹配段,也可以叫 Z-box.
算法的过程中我们维护右端点最靠右的匹配段.为了方便,记作 [𝑙,𝑟][l,r].根据定义,𝑠[𝑙,𝑟]s[l,r] 是 𝑠s 的前缀.在计算 𝑧[𝑖]z[i] 时我们保证 𝑙 ≤𝑖l≤i.初始时 𝑙 =𝑟 =0l=r=0.
在计算 𝑧[𝑖]z[i] 的过程中:
如果 𝑖 ≤𝑟i≤r,那么根据 [𝑙,𝑟][l,r] 的定义有 𝑠[𝑖,𝑟] =𝑠[𝑖 −𝑙,𝑟 −𝑙]s[i,r]=s[i−l,r−l],因此 𝑧[𝑖] ≥min(𝑧[𝑖 −𝑙],𝑟 −𝑖 +1)z[i]≥min(z[i−l],r−i+1).这时:若 𝑧[𝑖 −𝑙] <𝑟 −𝑖 +1z[i−l]
实现C++Python 1
2
3
4
5
6
7
8
9
10
11
12
13
14vector
int n = (int)s.length();
vector
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
15def 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 循环,每次执行都会使得 𝑟r 向后移至少 11 位,而 𝑟 <𝑛 −1r 对于外层循环,只有一遍线性遍历. 总复杂度为 𝑂(𝑛)O(n). 应用我们现在来考虑在若干具体情况下 Z 函数的应用. 这些应用在很大程度上同 前缀函数 的应用类似. 匹配所有子串为了避免混淆,我们将 𝑡t 称作 文本,将 𝑝p 称作 模式.所给出的问题是:寻找在文本 𝑡t 中模式 𝑝p 的所有出现(occurrence). 为了解决该问题,我们构造一个新的字符串 𝑠 =𝑝 + ⋄ +𝑡s=p+⋄+t,也即我们将 𝑝p 和 𝑡t 连接在一起,但是在中间放置了一个分割字符 ⋄⋄(我们将如此选取 ⋄⋄ 使得其必定不出现在 𝑝p 和 𝑡t 中). 首先计算 𝑠s 的 Z 函数.接下来,对于在区间 [0,|𝑡| −1][0,|t|−1] 中的任意 𝑖i,我们考虑以 𝑡[𝑖]t[i] 为开头的后缀在 𝑠s 中的 Z 函数值 𝑘 =𝑧[𝑖 +|𝑝| +1]k=z[i+|p|+1].如果 𝑘 =|𝑝|k=|p|,那么我们知道有一个 𝑝p 的出现位于 𝑡t 的第 𝑖i 个位置,否则没有 𝑝p 的出现位于 𝑡t 的第 𝑖i 个位置. 其时间复杂度(同时也是其空间复杂度)为 𝑂(|𝑡| +|𝑝|)O(|t|+|p|). 本质不同子串数给定一个长度为 𝑛n 的字符串 𝑠s,计算 𝑠s 的本质不同子串的数目. 考虑计算增量,即在知道当前 𝑠s 的本质不同子串数的情况下,计算出在 𝑠s 末尾添加一个字符后的本质不同子串数. 令 𝑘k 为当前 𝑠s 的本质不同子串数.我们添加一个新的字符 𝑐c 至 𝑠s 的末尾.显然,会出现一些以 𝑐c 结尾的新的子串(以 𝑐c 结尾且之前未出现过的子串). 设串 𝑡t 是 𝑠 +𝑐s+c 的反串(反串指将原字符串的字符倒序排列形成的字符串).我们的任务是计算有多少 𝑡t 的前缀未在 𝑡t 的其他地方出现.考虑计算 𝑡t 的 Z 函数并找到其最大值 𝑧maxzmax.则 𝑡t 的长度小于等于 𝑧maxzmax 的前缀的反串在 𝑠s 中是已经出现过的以 𝑐c 结尾的子串. 所以,将字符 𝑐c 添加至 𝑠s 后新出现的子串数目为 |𝑡| −𝑧max|t|−zmax. 算法时间复杂度为 𝑂(𝑛2)O(n2). 值得注意的是,我们可以用同样的方法在 𝑂(𝑛)O(n) 时间内,重新计算在端点处添加一个字符或者删除一个字符(从尾或者头)后的本质不同子串数目. 字符串整周期给定一个长度为 𝑛n 的字符串 𝑠s,找到其最短的整周期,即寻找一个最短的字符串 𝑡t,使得 𝑠s 可以被若干个 𝑡t 拼接而成的字符串表示. 考虑计算 𝑠s 的 Z 函数,则其整周期的长度为最小的 𝑛n 的因数 𝑖i,满足 𝑖 +𝑧[𝑖] =𝑛i+z[i]=n. 该事实的证明同应用 前缀函数 的证明一样. 练习题目luogu P5410【模板】扩展 KMP/exKMP(Z 函数)luogu P7114【NOIP2020】字符串匹配CF126B PasswordUVa # 455 Periodic StringsUVa # 11022 String FactoringUVa 11475 - Extend to PalindromeCodechef - Chef and StringsCodeforces - Prefixes and SuffixesLeetcode 2223 - Sum of Scores of Built Strings本页面主要译自博文 Z-функция строки и её вычисление 与其英文翻译版 Z-function and its calculation.其中俄文版版权协议为 Public Domain + Leave a Link;英文版版权协议为 CC-BY-SA 4.0. 本页面最近更新:2026/1/7 08:56:54,更新历史发现错误?想一起完善? 在 GitHub 上编辑此页!本页面贡献者:sshwy, StudyingFather, Enter-tainer, LeoJacob, countercurrent-time, H-J-Granger, minghu6, NachtgeistW, iamtwz, Ir1d, Tiphereth-A, weiyong1024, AngelKitty, c-forrest, CCXXXI, cjsoft, diauweb, Early0v0, ezoixx130, GekkaSaori, HeRaNO, Konano, LovelyBuggies, Makkiy, mgt, P-Y-Y, PotassiumWings, SamZhangQingChuan, Suyun514, Xeonacid, amlhdsan, Dfkuaid, ethanrao, GavinZhengOI, Gesrua, gi-b716, ksyx, kxccc, lychees, Marcythm, Menci, ouuan, Peanut-Tang, pengxurui, shawlleyw, shuzhouliu, SukkaW, TrisolarisHD本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用