用于模式搜索的 Z 函数
匹配字符串中的各个前缀
用于模式搜索的 Z 函数 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
另一种匹配工具
Z 函数是模式搜索中一种简洁的 KMP 替代方案。许多人觉得它更容易理解。✨
z[i] 的含义
对于每个索引，z[i] 表示从 i 开始、同时与整个字符串的某个前缀匹配的最长子串长度。
一个小例子
对于 aabaab，z 的值依次为 0,1,0,3,1,0。在索引 3 处，子串 aab 与前缀匹配，因此长度为 3。
Z 区间
我们记录一个窗口[l, r]，它表示目前找到的最右匹配区间。这样就能复用之前的比较结果。
l, r = 0, 0区间内部
当 i 位于区间内部时，您可以先复制一个已知的 z 值，但不能超过区间的右边界。
if i < r:
z[i] = min(r - i, z[i - l])延伸到区间之外
完成初始复制后，只要字符仍与前缀匹配，就继续逐个比较字符。
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1将区间向右滑动
如果匹配延伸到了更右侧，就更新 l 和 r，让后续索引能够复用这个区间。
if i + z[i] > r:
l, r = i, i + z[i]线性时间保证
这个区间只会向右移动，因此总工作量为O(n)。每个字符所产生的工作量都有上限。
使用 Z 进行搜索
拼接pattern + sep + text，然后运行 Z。任何等于模式长度的 z 值都表示一次匹配。
combined = pattern + chr(0) + text
z = z_function(combined)读取匹配结果
扫描 Z 数组；凡是满足z[i] == len(pattern) 的位置，匹配就从文本中相应的位置开始。
if z[i] == len(pattern):
matches.append(i - len(pattern) - 1)Z 与 KMP
Z 和 KMP 都能在线性时间内运行。Z 通常更容易编写，因此是您工具箱中很好的备用方案。
快速检查
确保您已经牢牢记住 Z 数组的含义。
回顾：Z 函数的优势
您使用滑动区间构建了Z 数组，在线性时间内完成搜索，现在又掌握了一种简洁的 KMP 替代方案。🎯
常见问题解答
「用于模式搜索的 Z 函数」课时是免费的吗？
是的 — 「用于模式搜索的 Z 函数」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「用于模式搜索的 Z 函数」这节课中我会学到什么？
匹配字符串中的各个前缀 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「用于模式搜索的 Z 函数」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- KMP 前缀函数
- 多项式字符串哈希
- 用于模式搜索的 Z 函数
- 使用字典树进行前缀查找