01先把问题说具体
对每个位置 i,求从 i 开始的后缀与整个字符串前缀的最长公共前缀长度。
02一步步得到方法
Z[i] 问的是起点,不是结束点
Z[i] 从位置 i 向右比较 s[i+k] 与 s[k];前缀函数 pi[i] 则关注以 i 结束的前缀的边界。两种数组都复用前缀信息,但定义不同,不能互换。
维护一个已知匹配区间 [left,right),它等于字符串前缀且右端最远。若 i 在其中,映射到前缀对应位置 i−left,已有 Z 值可借用,但最多借到 right−i。
为什么还要继续向右试探
若借来的长度没有触及已知右边界,下一次失配已由前缀对应位置保证,无需扩展;如果恰好到边界,外面未知,继续逐字符比较。实现中统一用 while 从借用长度开始尝试。
每次真正成功扩展都会把最右边界向右推进,而 right 最多推进 n 次;其他每个位置只做常数处理,因此总时间 O(n)。
右端最远的匹配窗口可以复用
Z[i] 表示从 i 开始的子串与整串前缀匹配多长。维护已知匹配窗口 [l,r),当 i 落在其中,可以借用前缀对应位置的 Z 信息,但最多借到 r−i。
若借用长度触及窗口右端,才需要继续逐字符向外检查。每次真正扩展都会推进全局最远右端,因此总扩展次数是线性的;窗口内截断信息则常数时间即可获取。
03把一个小例子完全算清楚
s='abacaba',约定 Z[0]=0。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| i=2 | 后缀 acaba 与前缀只匹配 a | Z[2]=1 |
| i=4 | 后缀 aba 完整匹配前缀 aba | Z[4]=3,区间 [4,7) |
| i=6 | 借用 Z[2],受边界限制为 1 | Z[6]=1 |
窄屏可左右滑动表格,阅读完整计算与理由。
完整结果 [0,0,1,0,3,0,1]。
04为什么这个方法成立
- 区间 [left,right) 始终已确认等于同长度前缀。
- 区间内映射的比较可复用,截断到 right 防止使用未知信息。
- 边界外逐字符扩展补齐全部匹配,因此每个 Z 值准确。
05把推导翻译成代码
Python · 可独立运行的教学实现
def z_function(s):
z = [0]*len(s)
left = right = 0
for i in range(1,len(s)):
if i < right:
z[i] = min(right-i,z[i-left])
while i+z[i] < len(s) and s[z[i]] == s[i+z[i]]:
z[i] += 1
if i+z[i] > right:
left,right = i,i+z[i]
return z逐个理解关键决定
min(right-i,z[i-left])- 只复用已证明范围内的信息,不能直接照抄镜像长度。
left,right = i,i+z[i]- 维护半开右端点,与 while 边界一致。
06时间、空间与实现范围
时间 O(n),Z 数组 O(n) 空间。
用 pattern+分隔符+text 搜索时,分隔符必须不出现在两边,或用带类型的哨兵序列避免字符冲突。
07改变条件,检查哪里会出错
把 Z[i] 当作前缀函数 pi[i]
先读定义:一个从 i 开始,一个以 i 结束,含义不同。
拼接模式与文本时分隔符也出现在输入
应选不出现在两边的分隔符或使用安全编码,否则匹配可能跨越错误边界。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
aaaa 的 Z 数组?
需要一点提示
每个后缀匹配前缀到结尾。
查看解析与答案
[0,3,2,1]。
为什么不能借用超过 right−i 的长度?
需要一点提示
区间外是否已经比较过?
查看解析与答案
没有,镜像匹配不自动证明外部字符相等,必须实际扩展。
如何用 Z 找模式串?
需要一点提示
拼接后找 Z 值足够长的位置。
查看解析与答案
对模式、独立分隔符、文本组成序列计算 Z,文本区中 Z≥模式长的位置就是匹配起点。