z-algorithm是一种线性时间预处理算法，用于计算字符串各位置与前缀的最长公共前缀长度（z值），通过构造z数组辅助子串匹配：将pattern+"$"+text拼接后运行该算法，若z[i]等于pattern长度，则text中对应位置发生完整匹配。
什么是Z-Algorithm，它和字符串匹配有什么关系
Z-Algorithm 不是标准库函数，而是一种线性时间预处理算法，用于计算一个字符串每个位置的「Z-value」：即从该位置开始与整个字符串前缀的最长公共前缀长度。它常被用来替代 KMP 实现子串匹配，但更直观、更易手写——尤其适合在竞赛或自定义匹配逻辑中快速实现。
关键点在于：Z-Algorithm 本身不直接“匹配”，而是通过构造 Z 数组辅助匹配。真正做模式匹配时，要把模式 pattern 和文本 text 拼成 pattern + "$" + text（用唯一分隔符），再对拼接串跑 Z-Algorithm；若某位置 i 的 Z[i] 等于 pattern.length()，说明此处发生了完整匹配。
如何手写Z数组计算（C++实现）
Z 数组计算必须严格 O(n)，不能暴力嵌套循环。核心是维护一个「当前最右覆盖区间」[L, R]，并复用已知信息避免重复比较。
常见错误是边界判断漏掉 R 或误用 <code>Z[i-L] 而不加限制：
- 当
i > R时，只能暴力向后扩展，更新L = i - 当
i 时，先取 <code>Z[i-L]，但最多只能复用到R-i+1长度，超出部分仍需暴力扩展 -
Z[0]定义为整个字符串长度（按惯例），但实际匹配时通常忽略它
示例（拼接串 s = "abababab"）：
vector<int> computeZ(const string& s) {
int n = s.size();
vector<int> Z(n);
Z[0] = n; // or 0, depending on convention — for matching, set Z[0]=0 is safer
int L = 0, R = 0;
for (int i = 1; i R) {
L = i;
R = i + Z[i] - 1;
}
}
return Z;
}</int></int>
怎么用Z数组做子串匹配（pattern in text）
拼接方式决定行为：必须用不可出现在 pattern 或 text 中的分隔符（如 '<p>拼接方式决定行为：必须用不可出现在 <code>pattern 或 text 中的分隔符（如 '\0' 或 '$'），否则可能产生跨边界的虚假匹配。
'$'），否则可能产生跨边界的虚假匹配。
匹配逻辑很简单：对 s = pattern + "$" + text 计算 Z 数组后，遍历 i 从 pattern.size()+1 开始（跳过分隔符和 pattern 自身），检查是否 Z[i] == pattern.size()。
注意点：
- 如果
pattern为空，要提前返回；如果含'$'，换其他分隔符 -
Z[i]对应的是s[i...]和s[0...]的 LCP，所以只有当i落在text区间内且Z[i]刚好等于 pattern 长度，才确认一次匹配 - 返回位置需减去
pattern.size() + 1（即 offset）
简短匹配封装：
vector<int> zSearch(const string& pattern, const string& text) {
if (pattern.empty()) return {};
string s = pattern + "$" + text;
vector<int> Z = computeZ(s);
vector<int> res;
int patLen = pattern.size();
for (int i = patLen + 1; i <h3>性能和边界问题容易踩哪些坑</h3>
<p>Z-Algorithm 理论 O(n)，但实际中几个细节会让它变慢或出错：</p>
<ul>
<li>分隔符选 <code>'\0'</code> 时，<code>string</code> 构造可能截断（C++ <code>std::string</code> 支持 null 字符，但 <code>cout 会提前终止）——建议用 <code>'$'</code> 或 <code>'#'</code></code>
</li>
<li>暴力扩展循环里没加 <code>i + Z[i] 判断，会导致越界访问</code>
</li>
<li>误把 <code>Z[0]</code> 当作有效匹配位（它对应整个串自身，不是 pattern 在 text 中的出现）</li>
<li>多模式场景下，Z-Algorithm 不如 AC 自动机或后缀数组高效；单次 pattern 多次 text 才值得预处理</li>
</ul>
<p>真正要注意的其实是拼接串的索引映射——稍一疏忽，<code>i - patLen - 1</code> 就会偏移一位，而这种 bug 在小样例里还表现不出来。</p></int></int></int>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
