假设我们想知道字符串前缀在每个较后位置重新出现多长。把每个后缀独立与前缀比较,做法正确,但高度重复的字符串会让同一关系被反复验证。全部字符相同时,这些独立扫描需要平方时间。
Z 数组记录所有这样的前缀匹配长度。它的线性时间计算复用一段先前已经验证的匹配区间,称为 Z-box。关键问题是这个区间究竟证明了多少。有时它完全确定新答案,有时它只给出下界,必须从右边界继续比较。
这个表示不同于 KMP 的前缀函数状态。我们将推导它自己的不变量,再用结果查找精确模式出现位置、后缀边界和周期。代码不依赖哈希或概率相等判断。
用明确边界定义匹配长度
设 为长度 的序列,从 0 开始编号。半开片段 包含位置 。元素使用一致的相等关系比较;下文处理字符串时,元素是 Python 字符串码位。不隐含大小写转换、Unicode 规范化或字素分组。
定义 9.2.1
(Z 值与第零位置的约定)
对 ,定义 为满足下列条件的最大长度 :
约定 ,不用它描述完整序列与自身的匹配。空序列的 Z 数组也为空。正位置的值为零,表示第一个元素已经不同。
上界 很重要:匹配不能越过后缀末端。如果 ,下一次比较失败,所以 ;如果 ,后缀已经耗尽,该侧不存在下一个可比较元素。
例如 aaaaa 的 Z 数组为 。即使所有可用元素都相同,后缀长度仍使数值递减。每次从零计算,会重复 次成功比较。
已知匹配区间提供两种不同信息
定义 9.2.2
(Z 区间)
依次处理 时,维护先前已验证的区间 ,满足
其右端点是先前已计算匹配达到的最远位置;最初 。所有较早的 Z 值都已精确。允许空区间。如果 ,旧区间不提供任何正长度信息,便从零开始直接比较。
如果 ,位置 在区间内。令 ,位置 对应前缀位置 ,而 已经算好。在区间范围内,可以安全复制
上限 是旧区间仍可提供的长度。它是已证明信息的边界,而不是断言真实匹配必定在这里停止。
定理 9.2.3
(区间复用)
设 ,,令 ,并设 已是精确值,记 。则 ,故 。若还有 ,则 。
证明
(把相等关系经区间搬过来)
对每个 ,区间等式给出 ,旧值 又给出 。因此前 个元素确实与前缀匹配。
如果 ,复制前缀之后的失配也位于旧区间内。精确旧值保证 ,区间等式把右侧元素对应为 。因此新匹配恰好在 停止,不可能更长。
如果 ,已知相等到达区间边界,但区间并未证明下一个元素。真实匹配可能在这里停止,也可能超过 。复制 个元素后,开始直接比较;遇到失配或序列末端便得到精确新值。如果新端点 超过 ,就把区间更新为 。
证明透视
上限把证明分成两种情形
上限 把两种用到不同类型事实的情形分开。当 时,证明用了两个等式(区间和旧 Z 值)和一个不等式,即经区间搬过来的旧失配;正是这个不等式固定了答案。当 时,只有等式可用,它们至多保证 个元素,却不保证任何不等式,这正是为什么必须从 重新开始直接比较。条件 保证使用 时它已是精确值。下面的反例显示去掉上限会出什么问题。
所引用的 是更早的值:循环中可用区间必从较早的正位置 开始,因此 。实现可以在复制后统一执行一个比较循环;内部失配情形下,第一次比较只是确认已知失败。
反例模式
超出旧区间复制,会虚构匹配元素
对 aaab,位置 1 的匹配长度为 2,因此区间变为 。在位置 2,、,但可用区间后段只有 。安全复制长度为一。
下一次比较是前缀 a 与最后的 b,所以 。直接复制旧值 2,会声称后缀 ab 匹配前缀 aa。旧值描述另一个位置的匹配,多出的元素位于这个区间所保证的相等范围之外。
同时展示两种复用情形
例题 9.2.4
(内部答案固定;边界答案可以增长)
取 aabcaabxaaaz,位置从 0 到 11。完整 Z 数组为 。以下选取步骤展示不同情形:
| 位置 | 比较前的信息 | 精确值 | 之后的区间 |
|---|---|---|---|
| 4 | 在旧区间外;将 aab 与前缀比较 | 3 | |
| 5 | 、;复制内部失配 | 1 | |
| 6 | 、 | 0 | |
| 8 | 在区间外;两个 a 匹配,之后 a 与前缀 b 不同 | 2 | |
| 9 | 复制 ,再比较位置 10 | 2 | |
| 10 | 复制一个至边界,再遇到最后的 z | 1 |
位置 9 复制的一个元素不是完整答案。下一个 a 还匹配前缀位置 1,所以长度增为二;最后的 z 再与前缀位置 2 的 b 失配。位置 5 则不同:失配已由区间内部信息保证,不可能成功延伸。
例题 9.2.5
(用尽的后缀,以及随后的区间)
abcabc 的 Z 数组是 。位置 1 和 2 立即失配,因为 b、c 都不同于 a。在位置 3,后缀 abc 与前缀相同并已用尽:,这同时显示边界 abc 与周期 3。此时区间是 。位置 4 的 ,而 ,所以直接搬用:。位置 5 的 ,,所以 。最后两个值除了已知的失配之外,不需要新的比较。
为什么所有比较工作都是线性的
定理 9.2.6
(线性时间的 Z 数组)
在索引与元素相等比较都是常数时间的假设下,这个循环计算长度为 的序列的 Z 数组,需时 、使用 个存储格。
证明
(把成功的比较记在位置上)
外层每次迭代只用常数工作选择初始长度。如果复制匹配严格在旧区间内结束,已知失配使其没有任何成功比较。否则,直接比较从旧右端点 或更后位置开始。
把每次成功比较记在其后缀侧位置上。同次迭代中,这些位置逐一增加;到迭代结束,新区间已经伸到每个这样的位置之后。因为 不会减小,后续迭代不可能再次在已记账位置成功比较。可记账的位置只有 1 到 ,至多 个。
每次迭代也至多有一次失败元素比较,因为循环在第一个失配处停止;序列耗尽则可能不用失败比较就停止。 时共有 次迭代,因此总元素比较次数与其余循环工作都是 。存在嵌套比较循环,并不说明这里必定需要平方时间。
证明透视
为什么区间右端是一个棘轮
每次成功的直接比较都发生在某个后缀位置 。在内部失配的情形下没有任何比较成功;在到达边界的情形下,比较从 开始;当 时,比较从 开始。迭代结束后 ,而 从不减少,所以 不可能再被成功比较。因此记账的对象是位置而不是迭代,这就是为什么外层循环里的内层循环不会使成本相乘。失败的比较每次迭代至多多一次。
Z 数组使用 个存储单元,区间本身只需要常数状态。这些界假设索引访问和元素相等比较都是常数时间。如果比较一个元素本身需要很长计算,复杂度也要重新分析。
用不会碰撞的分隔元素做精确匹配
设非空模式 长 ,文本 长 。把模式、一个全新分隔元素、文本接成一个元素序列。文本从偏移 开始。
定理 9.2.7
(由 Z 值得到出现位置)
设 非空、长 , 长 , 是序列 ,其中元素 不等于 或 的任何元素。对 ,有 ,并且 在 的下标 出现,当且仅当 。
证明
(全新分隔元素把每个值限制在 m 以内)
在文本下标 ,前 个元素与合并序列的前缀相同,当且仅当模式在 出现。全新分隔元素还保证这里的 Z 值不能超过 :匹配 个元素后,前缀提供分隔元素,而后缀提供文本元素,或者文本已经结束。因此 z[m + 1 + j] == m 是精确出现判定。
Python 字符串由字符元素组成,所以把新建的 object() 放入列表,就得到一个不等于任何字符元素的分隔元素。不必猜测某个特定字符,例如 #,是否未在两个输入中出现。下面的包装函数使用这个对象作分隔,按递增顺序返回出现下标,包括重叠出现。
def z_array(sequence):
n = len(sequence)
z = [0] * n
left = right = 0
for i in range(1, n):
if i < right:
z[i] = min(right - i, z[i - left])
while i + z[i] < n and sequence[z[i]] == sequence[i + z[i]]:
z[i] += 1
if i + z[i] > right:
left, right = i, i + z[i]
return z
def all_occurrences(pattern, text):
if pattern == "":
return list(range(len(text) + 1))
combined = list(pattern) + [object()] + list(text)
z = z_array(combined)
length = len(pattern)
offset = length + 1
return [i for i in range(len(text)) if z[offset + i] == length]
包装函数接受字符串;底层函数接受符合先前相等假设、有限且可索引的元素序列。两者都不修改输入。构建合并列表、计算 Z 数组与扫描文本位置,共需 时间和存储单元,包括至多 个位置的输出。空模式的指定结果是全部边界 ,在构造合并序列之前处理。
例题 9.2.8
(保留重叠出现,而不是消耗第一次匹配)
模式为 aba,文本为 ababa。展示时用 表示唯一分隔元素;这个符号代表对象,并非选定的输入字符。合并元素是 a b a、、a b a b a,Z 数组为 。
文本偏移为 。合并位置 4、6 的值都等于模式长度 3,因此结果为 。两次出现共享文本位置 2 的元素。从 Z 数组检查每个起点,可以保留这种重叠,而不是越过第一次完整出现再继续。
反例模式
普通分隔字符不能证明长度上限
假设模式 #、文本 ##,再用一个字面 # 分隔。合并结果为 ####,Z 数组是 。第一个文本位置的 Z 值为 2,而非模式长度 1,因为相等延续到了所谓分隔字符之后。
如果用等于模式长度的筛选,就会漏掉文本下标 0 的出现。使用大于或等于仍能找到它,但“这些 Z 值不超过模式长度”的断言已经不成立。全新对象建立了本实现实际使用的不变量;展示一个标点符号,并不能证明它唯一。
边界和周期使用同一批精确值
定理 9.2.9
(由 Z 值得到边界与周期)
设 长 ,。后缀 是 的真边界,当且仅当 ,此时其长度为 。对 , 是 的周期,当且仅当 。
证明
(把整个后缀与前缀比较)
非空真边界是同时为前缀和后缀、长度 满足 的片段。该后缀从 开始,判定为 :整个后缀匹配前缀。定义中的上界使这个位置不可能有更大值。扫描这些后缀起点,可以在线性时间列出所有真边界长度。
对 ,若每个 都满足 ,则称 是周期。这恰好是位置 的 次前缀对后缀比较,因此判定为 。 时完整长度 是平凡周期,但数组没有合法位置 z[n],不能用这个下标测试。
常见错误
(周期不等于完整重复)
周期不必整除长度。对 ababa,有 ,所以 2 是周期,即使字符串并非若干完整 ab 的拼接。若要求长度 块的完整重复,还需要 整除 。这区分了“下一份只写一部分就结束”的重复规律与完整份数的拼接。
常见错误
(Z 值不是 KMP 的边界长度)
共同有用的信息,是已经证明两个片段相等。Z 值不是任意子串较早出现的长度,也不是 KMP 在该位置结束的前缀之边界长度。每次使用时,都应保留它“前缀对当前后缀”的含义。
概念视角组合
从 Z 值读出前缀函数
对位置 , 的一个长度为 的真边界,起始于某个 ,并满足 ,即 。最长边界来自最小的这种 ,所以 ;若不存在这样的 ,则 。每个 Z 区间 列出了从 起始的边界仍然成立的结尾位置。
练习与完整解答
快速检查
(1. 取 z[0]=0,写出 aaaaa 的 Z 数组。找到区间 [1,5) 后,在位置 2 为什么不能不加上限地复制 z[1]=4?)
解答 · 1. 可用后缀限制能够复制的信息
数组是 。位置 2 的区间只提供 个元素,整个后缀也只有三个。复制 4 会越过序列末端。有上限的初始值为 ,而耗尽序列使它成为精确答案。
快速检查
(2. aabcaabxaaaz 中,为什么位置 5 的值恰好为 1,而位置 9 复制的 1 可以增长到 2?)
解答 · 2. 找到第一个未证明的比较
位置 5 的区间 还剩两个元素,但 严格在区间内结束。失配通过区间被搬到新位置,答案固定为 1。位置 9 的区间 却只剩一个元素,所以复制的 1 到达边界。位置 10 是新信息,其 a 匹配前缀位置 1,长度增为 2,之后最终的 z 才与前缀 b 失配。
快速检查
(3. 在文本 ababa 中查找模式 aba,合并文本偏移是多少?哪两个合并 Z 值证明出现位置?为什么不跳过下标 2?)
解答 · 3. 把合并下标还原为文本下标
偏移为 。合并位置 4、6 的 Z 值为 3,产生文本起点 和 。方法检查每个文本起点,而不是消耗一次匹配就跳过整个模式长度,所以保留了重叠出现。
快速检查
(4. 用字面 # 作分隔时,为什么在文本 ## 查找模式 # 会让等于长度的筛选失败?object() 的什么性质恢复了实现的证明?)
解答 · 4. 证明唯一,而不是假设某字符缺席
合并字符串是 ####,第一个文本 Z 值为 2,所以即使这里有匹配,等于模式长度 1 的判断仍然失败。全新对象元素不等于任何字符串字符。模式匹配完毕后,下一个前缀元素是对象,后缀则已耗尽或提供字符,因此匹配不能超过一。两个文本起点的 Z 值都会成为 1。
快速检查
(5. 空模式在文本 ab 中,all_occurrences 应返回什么?非空模式配空文本,以及模式长于文本时,又如何?)
解答 · 5. 空匹配位于边界
空模式配 ab 的结果为 ,每个边界一个。非空模式在空文本中没有出现,返回 。模式长于文本也返回 ,因为任何剩余文本后缀都无法提供所需的元素数。这些结果来自包装函数的明确约定和后缀长度上限,不必改变 的含义。
快速检查
(6. ababa 的 Z 数组为 [0,0,3,0,1],求非空真边界长度。2 是否为周期?字符串是否由长度二块的完整份数组成?)
解答 · 6. 周期可以在不完整的一份结束
位置 2、4 分别以长度 3、1 耗尽其后缀,所以真边界长度为 和 。由 ,2 是周期。但 2 不整除 5,因此字符串不能由完整长度二块拼接而成;它沿着 ab 的重复规律,只写到下一份的第一个元素为止。