引言
在字符串算法中，Z 函数（也称 Z-Algorithm）是一种经典且高效的预处理技术，能够在 O(n) 时间内计算一个字符串的 Z 数组。Z 数组在模式匹配、重复子串查找、最长公共前缀（LCP）查询等场景中有着广泛应用。本文将从基本定义、核心思想、线性算法流程、代码实现以及典型应用等方面，带你深入理解 Z 函数。
一、Z 函数的定义
给定字符串 S（长度为 n），其 Z 数组 Z[0…n-1] 定义为：
- Z[0] 通常设为 0（或 n），在实际算法中不使用。
- 对于 i>0，Z[i] 表示子串 S[i…] 与 S[0…] 的最长公共前缀（LCP）的长度。
示例：
S = "aabxaabxcaabxaabxay"
索引 i: 0 1 2 3 4 5 6 7 8 9 ...
字符 S: a a b x a a b x c a ...
Z 值 Z: - 1 0 0 4 3 2 1 0 1 ...
二、核心思想：
Z-Box 优化为了避免暴力匹配的 O(n^2) 开销，Z 算法引入了一个“Z-Box”区间 [l, r]：
- 该区间表示已知 S[l…r] 与 S[0…r-l] 完全匹配，并且 r 是最右匹配到的位置。
- 对于下一个位置 i，如果 i 在 Z-Box 内（i ≤ r），可以通过镜像位置 k = i - l 的已知 Z[k] 值，快速确定 Z[i] 的初始值；否则，需要从头开始匹配。
如下图所示，对于
I - L和I开始的部分，我们已知[I - L : R - L]和[I : R]是相同的，而[I - L : I - L + Z[I - L]]部分又和字符串的前缀相同，那么可以知道[I : R]和字符串前缀相同，或者部分相同，因此可以根据Z[I - L]的大小，得到Z[I]的大小。
三、代码实现
// Leetcode3031
class Solution {
public:
int minimumTimeToInitialState(string word, int k) {
int N = word.length();
// Z函数数组
vector<int> Z(N);
int L = 0, R = 0;
for (int I = 1; I < N; ++I) {
// 根据Z[I - L]的大小，来确定Z[I]的值
if (I < R && Z[I - L] < R - I + 1) {
Z[I] = Z[I - L];
} else {
Z[I] = max(0, R - I);
while (I + Z[I] < N && word[I + Z[I]] == word[Z[I]]) {
++Z[I];
}
L = I;
R = I + Z[I] - 1;
}
if ((I % k == 0) && (Z[I] == N - I)) {
return I / k;
}
}
return (N + k - 1) / k;
}
};
时间复杂度：O(n)空间复杂度：O(n)
四、Z 数组与 KMP 算法中 next 数组的关系
Z 函数与 KMP 中的 next 数组虽然思路不同，但它们都在进行字符串的“前缀-后缀”匹配。
- Z[i] 表示： 从位置 i 开始的后缀与整个字符串前缀的最长公共前缀长度。
- KMP 的 next[i] 表示： 字符串 s[0:i] 的真前缀和真后缀的最长匹配长度。 二者的核心区别在于：
- Z 函数关注的是任意位置 i 开始的后缀与整体前缀的匹配。
- KMP 的 next 数组只考虑前缀自身的匹配，不涉及其他位置。 在构造方式上：
- Z 数组可以用于构造 next 数组：如果我们反向构造 Z 值，可以获得部分匹配信息；
- 在某些题目中，可以通过构造字符串 “P + # + T” 并计算其 Z 值来模拟 KMP 的匹配过程。尽管实现路径不同，但它们都在追求一个目标：利用已有信息减少重复匹配。