形式陈述

对字符串 $s$，定义 $Z[i]$ 为 $s[i..]$ 与 $s[0..]$ 的最长公共前缀长度，通常约定 $Z[0]=0$ 或 $n$。 线性算法维护当前最右的匹配区间 $[l,r)$；若 $i<r$，先复用 $Z[i-l]$ 的已知部分，再向右显式扩展。每次字符比较导致右端点推进，故总时间 $O(n)$。

直觉

已知一段文本与前缀相等时，区间内部的位置可以借用前缀自身的匹配信息，只有越过右边界才需新比较。

例子与边界

对模式 $p$ 与文本 $t$，在 $p\mathrm{\#}t$ 上计算 Z 值即可找匹配。分隔符必须不出现在字母表中；不同资料对 $Z[0]$ 的约定不同。

推论与应用

它与前缀函数提供互补的 border 信息，并用于模式匹配、周期和字符串比较。

参考资料

• OI-Wiki contributors, OI-Wiki (2026), Z-function.
• cp-algorithms contributors, Algorithms for Competitive Programming (2026), Z-function.