Z 函数

Z 函数 $Z[i]$ 记录从位置 $i$ 开始的后缀与整个字符串前缀的最长匹配长度。线性算法维护当前最右匹配区间 $[l,r)$：已知区间内文本与前缀相等时，位置 $i$ 可先借用镜像位置的匹配下界，只有越过右边界才需继续比较。每次显式字符比较要么失败，要么推进全局右边界，因此总成本线性。

字符串 aabcaabxaaaz 的某些位置会有较大 Z 值；更简单地，aaaaa 的 Z 数组（约定 $Z[0]=0$）为 $[0,4,3,2,1]$。模式匹配可计算 pattern#text 的 Z 值，凡 $Z[i]=|pattern|$ 的文本位置即为出现点。

$Z[0]$ 有定义为 $0$ 或 $n$ 的不同惯例，代码和公式需统一。分隔符必须不在原字母表中；复用区间时只能取 $min(r-i,Z[i-l])$，越过右边界的部分仍要实际比较。

词公理库字Word · String从某个有限位置集到字母表的函数，即有限符号序列。与序列公理库序列Sequence以自然数为定义域的函数。提供对象。Z 函数在给定串上以确定性最坏 $O(n)$ 时间、$O(n)$ 额外整数空间提取前缀匹配长度；它与前缀函数公理库前缀函数Prefix function · Failure function记录每个前缀的最长真前缀—后缀重合长度的字符串函数。提供互补的 border 信息并可线性互相转换，也用于周期与前缀出现次数。

在 pattern#text 上运行 Z 算法仍是一次模式—文本扫描。固定文本上反复查询时，FM-index公理库FM-indexFM-index · Full-text minute-space index · 压缩全文索引在压缩 BWT 上提供 rank 支持，以反向搜索完成模式计数，并通过采样后缀数组和逆后缀数组实现定位与文本提取。预处理 BWT 与 rank 结构，以压缩空间提供 count，定位还需额外采样；Z 数组既不保存后缀次序，也不能直接替代 backward search。两者都能找精确出现位置，但预处理对象和查询成本完全不同。