专题进阶 · 字符串算法推荐总顺序 · 第 86 / 148 课

用已知匹配区间复用前缀比较,区分 Z 值与前缀函数。

先学会这些,再进入本课 KMP
还有 1 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 字符串算法

Z 算法Z Algorithm

Z[i] 表示从 i 开始与全串前缀匹配的长度,维护已知匹配区间做到线性。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

用已知匹配区间复用前缀比较,区分 Z 值与前缀函数。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

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 与前缀只匹配 aZ[2]=1
i=4后缀 aba 完整匹配前缀 abaZ[4]=3,区间 [4,7)
i=6借用 Z[2],受边界限制为 1Z[6]=1

窄屏可左右滑动表格,阅读完整计算与理由。

完整结果 [0,0,1,0,3,0,1]。

04为什么这个方法成立

  1. 区间 [left,right) 始终已确认等于同长度前缀。
  2. 区间内映射的比较可复用,截断到 right 防止使用未知信息。
  3. 边界外逐字符扩展补齐全部匹配,因此每个 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从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

aaaa 的 Z 数组?

需要一点提示

每个后缀匹配前缀到结尾。

查看解析与答案

[0,3,2,1]。

练习 2 · 边界与辨析

为什么不能借用超过 right−i 的长度?

需要一点提示

区间外是否已经比较过?

查看解析与答案

没有,镜像匹配不自动证明外部字符相等,必须实际扩展。

练习 3 · 变式与迁移

如何用 Z 找模式串?

需要一点提示

拼接后找 Z 值足够长的位置。

查看解析与答案

对模式、独立分隔符、文本组成序列计算 Z,文本区中 Z≥模式长的位置就是匹配起点。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 字符串算法

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。