Z 函数（扩展 KMP）

字符串 · Z-box · 每个后缀跟开头像多久

一个数组回答所有「像不像开头」

Z 函数：z[i] = 整串 s 与后缀 s[i..] 的最长公共前缀（LCP）长度—— 「从 i 开始，跟串的开头能像多久」。它是 KMP 部分匹配表 π 的孪生兄弟（一个看前缀多长的后缀、一个看后缀多像前缀，可互相推出），而且语义更直白。朴素做法每个 i 都从零比起，O(n²)。

Z-box：能抄就抄，出界才比

加速的抓手叫 Z-box：记住最右的一段匹配 [l, r)（它是某个 z 的匹配段、也是串前缀的复制品）。i 落在 box 里时，i 在 box 中的相对位置 i−l 处「开头怎样」早就算过——抄镜像 z[i−l]（最多抄到 box 右缘 r−i）：

①box 外：没得抄，老实逐位右扩。
②镜像 < 余量：z[i−l] 在 box 里就断了，答案直接抄，零比较。
③镜像达界：抄到 box 右缘还在匹配——右缘外 box 管不着，继续右扩，扩多远算多远，然后把 box 刷新到这段新匹配。
O(n) 的账本：每次成功比较都推进 r，而 r 永不回退——总比较 ≤ n 次。

下图上行是 s、下行是逐格点亮的 z 数组；浅蓝带 = 当前 Z-box，琥珀环 = 当前 i，蓝环 = 镜像位置，绿 = 当前匹配段。右侧代码随步同步高亮。

z[i] = 整串 s 与后缀 s[i..] 的最长公共前缀（LCP）长度——「每个后缀跟开头像多久」。朴素做法每个 i 从零比起 O(n²)；Z-box 记住最右匹配区间 [l, r)，能抄就抄。z[0] = 整串比自己 = 7

1function zFunction(s: string): number[] {
const n = s.length;
const z = new Array(n).fill(0);
z[0] = n;                                    // 整串比自己
let l = 0, r = 0;                            // Z-box [l, r)
for (let i = 1; i < n; i++) {
  if (i < r) z[i] = Math.min(r - i, z[i - l]);   // box 内：抄镜像（截断到余量）
  while (i + z[i] < n && s[z[i]] === s[i + z[i]]) {
    z[i]++;                                  // 右扩：box 外或达界才会走到
  }
  if (i + z[i] > r) { l = i; r = i + z[i]; } // 推进最右 box
}
return z;                                    // O(n)：r 只增不减
14}

saabaaab

目标z[1..6]，全部 O(n) 算完

1 / 9

拿它做什么

最经典的用法是模式匹配：找 P 在 T 中的出现，对拼接串 P#T 求 Z（# 是不出现的分隔符，挡住跨界匹配），凡 z[i] = |P| 处即一次命中——和 KMP 同为 O(n+m)，但推导几乎零门槛。还有周期性判定（若 i + z[i] = n，则 s 以前 i 个字符为周期循环——最小的这样的 i 就是最小周期）、字符串压缩、与 π 表互算。三兄弟各有绝活：π 适合流式匹配（KMP）、Z 语义最直白、后缀数组（构造·LCP）打持久战；而 Z-box 的「区间内抄镜像」和 Manacher 的最右回文带是同一招——本页可视化直接复用了它的画布。

算法可视化

Z 函数（扩展 KMP）

一个数组回答所有「像不像开头」

Z-box：能抄就抄，出界才比

拿它做什么