扩展 KMP/exKMP（Z 函数）学习笔记

声明

本文章转载自 shangruolin 的博客，已经过作者（存疑）同意，帮TA宣传一下。

扩展 KMP/exKMP（Z 函数）学习笔记兼 P10479 匹配统计 题解。

LCP：最长公共前缀。

Z 函数，又称扩展 KMP（exKMP），能够在 \(O(n)\) 的时间内求出一个字符串与其所有后缀的 LCP 的长度。

定义 \(z_i\) 为字符串 \(s\) 与字符串 \(s\) 从第 \(i\) 位开始的后缀的 LCP 长度。

那么求解 \(z_i\) 便是我们的目标。直接暴力匹配复杂度为 \(O(n^2)\)。二分枚举长度再用哈希判断可以做到 \(O(n\log n)\)，足以通过本题。使用 Z 函数求解便可做到 \(O(n)\) 求解。

假设现在已经求出了 \(z_1\sim z_{i-1}\)，想要求解 \(z_i\)。

定义 \(r\) 为 \(r\) 最大的匹配子串的右端点，\(l\) 为 \(r\) 最大的匹配子串的左端点。

那么如果 \(i\le r\)，\(z_i\) 为 \(\min(z_{i-l+1},r-i+1)\)。通俗的解释一下：由定义知，\(s_{l}\sim s_{i-1}\) 与 \(s_1\sim s_{i-l}\) 是匹配的，则
\(s_i\sim s_r\) 与 \(s_{i-l+1}\sim s_{r-l+1}\) 是匹配的，那么 \(z_i\) 可以由 \(z_{i-l+1}\) 继承而来。但是我们并不知道 \(s_{r+1}\) 与 \(s_{r-i+2}\) 是否匹配，所以 \(z_i\) 需要对 \(z_{i-l+1}\) 和 \(r-i+1\) 取 \(\min\)。

接着，我们尝试进行暴力匹配，如果 \(s_{i+z_i}\) 与 \(s_{z_i+1}\) 相同，就让 \(z_i\) 加 \(1\)。

暴力匹配完后更新 \(l,r\) 即可。

Z 函数的复杂度是 \(O(n)\) 的，因为每个字符至多被暴力匹配 \(1\) 次。

求解 \(z\) 数组的代码：

z[1] = m; // 完全匹配
for (int i = 2, l = 0, r = 0; i <= m; i++) {
	if (i <= r) z[i] = min (z[i - l + 1], r - i + 1); // 获取初值
	while (i + z[i] <= m && b[i + z[i]] == b[z[i] + 1]) z[i] ++; // 暴力匹配
	if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1; // 更新 l, r
}

同样，我们定义 \(p_i\) 为为字符串 \(b\) 与字符串 \(a\) 从第 \(i\) 位开始的后缀的 LCP 长度。

则类似的，可以得到求解 \(p_i\) 的代码：

for (int i = 1, l = 0, r = 0; i <= n; i++) {
	if (i <= r) p[i] = min (z[i - l + 1], r - i + 1);
	while (i + p[i] <= n && a[i + p[i]] == b[p[i] + 1]) p[i] ++;
	if (i + p[i] - 1 > r) l = i, r = i + p[i] - 1;
	cnt[p[i]] ++; // 统计答案
}

对于每个询问，若询问长度为 \(x\)，则输出 \(cnt_x\)。

完整代码：

for (int i = 1, l = 0, r = 0; i <= n; i++) {
	if (i <= r) p[i] = min (z[i - l + 1], r - i + 1);
	while (i + p[i] <= n && a[i + p[i]] == b[p[i] + 1]) p[i] ++;
	if (i + p[i] - 1 > r) l = i, r = i + p[i] - 1;
	cnt[p[i]] ++; // 统计答案
}

本文没有图解，对初学者来说可能比较抽象。想要更好理解 Z 函数的同学可以前往 P5410 【模板】扩展 KMP/exKMP（Z 函数） 的题解区学习。

大家有任何建议或疑惑都可以在评论中提出，感谢！