illegalCreed

中文

English

中文

English

Appearance

Z 函数：扩展 KMP ​

基于通用算法套路 · 核于 2026-07

速查 ​

  • 目标：对串 s（长度 n），O(n) 构造 Z 数组 z[0..n-1]，其中 z[i] = s 与 s[i:] 的最长公共前缀长度；z[0] 通常约定为 0（或 n，本站按 0 处理）。
  • 示例：s = "aabaa" → z = [0, 1, 0, 2, 1]；s = "ababa" → z = [0, 0, 3, 0, 1]。
  • 核心思想（Z-box 加速）：维护当前已触及最右的「匹配段」[l, r]（满足 s[l..r-1] === s[0..r-l-1]，即这段是串的前缀），当前下标 i 落在 r 内时，从镜像 i-l 的已知 Z 值起步扩展。
  • 借初值公式：i < r 时 z[i] = min(z[i-l], r-i) 起步；i >= r 时 z[i] = 0 起步；然后 while (s[i+z[i]] === s[z[i]]) z[i]++。
  • 更新 l、r：若 i + z[i] > r，则 l = i, r = i + z[i]（向右扩展了 Z-box）。
  • O(n) 证明：r 单调右移、总推进 ≤ n；每次「成功的字符比较」都让 r 右移至少 1，失败比较每个 i 最多 1 次，总比较 ≤ 2n。
  • 应用①字符串匹配：构造 pat + '#' + txt 的 Z 数组，z[i] == |pat|（i 在 txt 部分）处即一个匹配点，整体 O(n+m)。
  • 应用②最小周期：最小的 p 满足 z[p] == n - p，则串是长度 p 的循环节重复；若还要 n % p == 0 则是完全周期。
  • 应用③重复子串/后缀关系：z[i] == n - i 表示后缀 s[i:] 恰是整串前缀（border 关系）。
  • 对比 KMP：KMP 的 next[i] 是「s[0..i] 的最长相等前后缀」；Z 函数直接给「s[i:] 与整串的公共前缀」——后者更直观，求匹配/周期更顺手，故称「扩展 KMP」。
  • 易错：z[0] 约定要统一；min(z[i-l], r-i) 的 r-i 是「Z-box 余量」不可漏；匹配应用里分隔符必须不在字符集内。

一、定义与示例 ​

Z 函数（Z-function）又称 扩展 KMP（extended KMP）。对长度为 n 的串 s，定义：

z[i] = s[0..] 与 s[i..] 的最长公共前缀长度（即从 i 起的后缀，与整串前缀最多匹配多少个字符）

约定 z[0] = 0（整串与自身的 LCP 是整串长度 n，但这个值无用且会干扰循环，故按 0 处理；也有教材约定 z[0] = n，仅差一处特判）。几个例子：

s = "aabaa"   →  z = [0, 1, 0, 2, 1]
                   ^  ^     ^  ^
                   |  |     |  s[4:]="a"，与 s 公共前缀 "a" 长 1
                   |  |     s[3:]="aa"，与 s 公共前缀 "aa" 长 2
                   |  s[1:]="abaa"，与 s 公共前缀 "a" 长 1
                   z[0] 约定 0

s = "ababa"   →  z = [0, 0, 3, 0, 1]
                   s[2:]="aba"，与 s="ababa" 公共前缀 "aba" 长 3

二、Z-box 加速：核心三步 ​

朴素构造是 O(n²)（每个 i 从 0 扩展）。Z 函数用「维护最右匹配段」做到 O(n)。维护两个量：

  • l：当前已触及最右的「匹配段」（满足 s[l..r-1] === s[0..r-l-1]）的左端。
  • r：该匹配段的右端（开区间，即第一个还没确认匹配的位置）。

这个 [l, r) 段叫 Z-box——它本身就是串的一个前缀，所以 i 落在 r 内时，i 关于 l 的镜像 i - l 处的 Z 值可以借用。对每个 i（从 1 开始）：

  1. 借初值：i < r 时，z[i] = min(z[i - l], r - i)。z[i-l] 是镜像位置的已知值（s[i..] 与 s[i-l..] 同构于 s[0..] 与 s[i-l..] 的已算关系）；r - i 是「Z-box 余量」（超过 r 的部分没法保证，要老老实实扩展）。i >= r 时 z[i] = 0。
  2. 向右扩展：while (i + z[i] < n && s[z[i]] === s[i + z[i]]) z[i]++。
  3. 更新 l、r：若 i + z[i] > r，则 l = i, r = i + z[i]（Z-box 右扩）。
js
// Z 函数：O(n) 构造 Z 数组
function zFunction(s) {
  const n = s.length;
  const z = new Array(n).fill(0);
  let l = 0, r = 0;                   // Z-box：[l, r) 是已知的匹配段（等于 s 前缀）
  for (let i = 1; i < n; i++) {
    if (i < r) z[i] = Math.min(z[i - l], r - i); // 借镜像初值
    while (i + z[i] < n && s[z[i]] === s[i + z[i]]) z[i]++; // 扩展
    if (i + z[i] > r) { l = i; r = i + z[i]; }    // 更新 Z-box
  }
  return z;                           // z[0] 保持 0
}

三、O(n) 摊还分析 ​

与 Manacher 完全同构的证明：r 单调右移、总推进 ≤ n。

  • 每次 while 成功匹配一次（s[z[i]] === s[i+z[i]] 成立），i + z[i] 至少 +1，更新后 r 也至少 +1——而 r ≤ n，所以成功比较 ≤ n 次。
  • 借初值保证了「r 以内的比较不必重做」；失败的比较（while 退出那一次）每个 i 最多 1 次，共 ≤ n 次。

总计字符比较 ≤ 2n，O(n)。这是「单调右端点 + 镜像借用 + 摊还」模板的又一实例。

四、应用一：字符串匹配 ​

把模式串 pat（长 m）和主串 txt（长 k）用字符集外的分隔符 # 拼起来，对拼接串 pat + '#' + txt 求 Z 数组：

  • 在 txt 部分（下标 i >= m + 1），若 z[i] === m，则说明 txt 中对应位置起、长度 m 的子串与 pat 完全相同——找到一个匹配点。
  • 整体 O(n + m)（拼接串长 m + 1 + k），与 KMP 同阶，但代码更短、推导更直观。
js
// 字符串匹配：返回 txt 中所有匹配 pat 的起始下标
function zMatch(txt, pat) {
  const concat = pat + '#' + txt;
  const z = zFunction(concat);
  const m = pat.length, res = [];
  for (let i = m + 1; i < concat.length; i++) {
    if (z[i] === m) res.push(i - (m + 1)); // 还原回 txt 的下标
  }
  return res;
}

五、应用二：最小周期与重复子串 ​

  • 最小循环节：最小的正整数 p，使得 s 可由其前 p 个字符重复若干次得到。用 Z 函数判定：若 z[p] === n - p（即 s[p..] 与 s 的公共前缀正好覆盖到串尾），则 p 是一个「弱周期」（s 是 s[0..p-1] 重复后可能截断的串）；若还满足 n % p === 0，则是「完全周期」（整数次重复）。最小的这种 p 即最小周期。
  • 后缀是前缀（border）：z[i] === n - i 表示后缀 s[i..] 恰好等于整串前缀 s[0..n-i-1]——这给出串的所有 border（相等的前后缀）长度，与 KMP 的 next 数组等价但视角不同。
  • 判重复子串：如「s 是否由某个子串重复多次构成」——找最小 p 使 z[p] === n - p 且 n % p === 0，若存在则 s = s[0..p-1] 重复 n/p 次。

交互演示 ​

下一步 ​

Manacher 与 Z 函数都讲完了，两者共用「单调右端点 + 镜像借用」的线性算法精髓。若要查阅复杂度表、完整代码、应用清单与易错点速查，见参考。