核心概述
Z 函数在 O(n) 时间计算每个位置起始后缀与整串的最长公共前缀长度，常用于单模式匹配、周期性分析与结构判定。
原文引述
Description: Z[i] = length of longest prefix of s that matches substring starting at i. Compute O(n). Used for pattern matching, period detection, and palindrome queries (with reversed string). ——来源：本节点英文注释 Time: O(n) ——来源：本节点英文注释 Status: tested ——来源：本节点英文注释
展开阐述
-
定义与背景
- 对字符串 s，Z[i] 表示 s[i..] 与 s[0..] 的最长公共前缀长度（通常取 Z[0]=0 或 n，具体按实现约定）。
- 通过维护当前“最右匹配区间”实现线性比较上界，常与 KMP 作为等价单模式匹配技术互为参照。
-
接口/字段/数据结构与输入输出语义（按仓库约定）
- vector
zFunction(const string& s) - 返回长度为 n 的 Z 数组；Z[i] ∈ [0, n−i]。
- vector
zSearch(const string& text, const string& pattern) - 基于 Z 的单模式匹配，返回所有出现位置（0-index，升序）。
- 典型模式匹配构造：t = pattern + ’$’ + text（分隔符不在字符集内），在 t 上求 Z，检测等于 |pattern| 的位置即匹配起点。
- vector
-
核心流程与关键要点（线性计算）
- 初始化 Z[0]=0（或 n），l=0, r=0 表示当前最右匹配区间 [l, r]。
- 对 i=1..n−1：
- 若 i ≤ r，则先设 Z[i] = min(r−i+1, Z[i−l]) 复用区间内信息；
- 再向右扩展 while (i+Z[i] < n 且 s[Z[i]] == s[i+Z[i]]) Z[i]++；
- 若 i+Z[i]−1 > r，则更新 l=i, r=i+Z[i]−1。
- 可证明字符比较总次数不超过 2n，因而线性。
-
复杂度与边界条件、常见变体/扩展
- 时间/空间：计算 O(n)，空间 O(n)。
- 边界：空串/单字符；Z[0] 的取值（0 或 n）不影响应用，但需在下游使用时保持一致。
- 变体：用反串配合 Z 进行回文判定；最小周期可由 n−Z[i] 与整除关系快速得到。
-
使用与注意
- 字符集仅需可判等；索引通常为 0-index。
- 单模式匹配与 121-字符串-KMP 等价；多模式场景建议使用 118-字符串-AC自动机。
- 与哈希法的等价判定对比：Z 为确定性且无碰撞风险，可与 119-字符串-字符串哈希 互补使用。
- 与后缀结构：全局子串关系/排序可参考 124-字符串-后缀数组、125-字符串-后缀树。