在文本中搜索时,我们常常发现模式串的开头已经匹配了若干字符,却在下一个字符处失败。若从文本的下一个位置重新开始,就丢弃了已有的信息:已经匹配部分的某个后缀,也许已经是模式串的另一个前缀。KMP 恰好记录了这些可以重用的前缀。
关键并不只是让下标更快地往回移动。每次回退都必须保留一个关于已读字符的准确断言。我们将从边界推导回退规则,证明总比较次数为何是线性的,并说明报告重叠出现时需要怎样重置状态。
边界既是前缀也是后缀
定义 9.1.1
(真边界与前缀函数)
对于长度为 的非空字符串 ,真边界(也称真前后缀)是一个同时为前缀和后缀、且长度严格小于 的字符串。允许长度为零的空串。
对从零开始编号的模式串 ,定义 为前缀 的最长真边界的长度。因此 ,且 。
本节所有下标和报告的匹配位置都从零开始。用 Python 记号表示, 是 P[:i + 1]。
对于 ababa,非空真边界是 a 和 aba,长度分别为 1 和 3。整个字符串本身也是前缀和后缀,但“真”排除了它。ab 和 abab 都不是后缀。边界要求整个子串相等,而不只是首字符或末字符相等。
引理 9.1.2
(边界的边界)
设 是字符串 的真边界,长度为 。对每个 , 是 的边界长度,当且仅当它是 的边界长度。因此,对模式串 ,数列 (只要项为正就继续)按递减次序列出 的全部真边界长度,最后是 。
证明
(较短的边界包含在最长边界之中)
设 是 的一个长度为 的边界。对于任意 ,由于 是前缀, 的长度为 的前缀等于 的长度为 的前缀。又由于 是后缀, 的长度为 的后缀等于 的长度为 的后缀。
因此, 是 的边界长度,当且仅当它是 的边界长度。特别地,在长度为 的最长边界之后,下一个可能的较短边界就是该边界自身的最长真边界。
长度为 的模式串边界是字符串 P[:j],它的最长真边界长度为 。反复沿这些值回退,便按递减顺序列出所有较短的边界长度,最终到达零。
通过延长已有边界构造前缀函数
假设 已知,令 。之前的前缀已经以 P[:j] 结尾。如果新字符 等于 ,这个边界就能延长到长度 。
如果字符不同,之前较短的边界仍有可能延长。由边界引理,下一个候选是 。重复此过程,直到成功延长或 。在零处与 比较:匹配则得到长度一,不匹配则得到长度零。
定理 9.1.3
(前缀函数的递推式)
对 ,令 ,并在 时令 ,使这条链止于 。则 ,其中 是链上第一个满足 的项;若链上没有项满足 ,则 。
证明
(第一次成功的延长就是最长的)
的任意一个长度为 的非空真边界,在去掉最后一个字符后,会成为前一个前缀的边界。这个先前边界的长度是 。要把它延长,最后必须比较 与 。
算法从先前最长的边界开始,沿完整的递减边界链依次检查。每个失败的候选都被必要的字符比较排除。因此第一次成功的候选给出了可能的最长新边界。如果没有候选能够延长,就只剩下空边界。这就按 归纳证明了递推规则。
例题 9.1.4
(一次失配可能需要多次边界回退)
模式串 ababaca 的表如下:
| 下标 | |||||||
|---|---|---|---|---|---|---|---|
| 字符 | a | b | a | b | a | c | a |
处理下标 5 之前,前缀 ababa 的最长边界是长度为 3 的 aba。新的 c 与 不匹配,于是回退到 。它也与 不匹配,再回退到 。它仍与 不匹配,因此 。
候选长度依次为 ,它们都是之前匹配的字符串实际具有的边界长度。接下来的 a 则开始一个长度为一的新边界。
在文本扫描中维持同一个不变量
设模式串长度为 ,文本长度为 。在处理两个文本字符之间,保持 等于满足以下条件的最长模式串前缀的长度:该前缀长度严格小于 ,并且是目前已读文本的后缀。初始时 。
对下一个文本字符,将它与 比较。如果失配且 ,将 替换为 ,并用同一个文本字符再次尝试。如果匹配,就把 加一。在零处失配则保持零。
如果 ,说明一个完整匹配刚好在文本下标 处结束,其起点为 。报告这个起点,然后在读取下一个文本字符前令 。
定理 9.1.5
(扫描不变量与所报告的出现位置)
采用上述失配回退与完整匹配后的重置,则在读入文本字符之间, 是“长度小于 且为已读文本后缀的最长模式前缀”的长度;并且每个出现位置恰好在读入其最后一个字符时被报告一次。
证明
(回退和重置恰好保留有用的后缀)
读取新字符之前,已经匹配的后缀是 P[:j]。任何同时是已读文本后缀的更短模式串前缀,都必须是这个已匹配字符串的边界。因此,边界链列举了所有可能的较短状态,无须重新读取先前的文本字符。
成功延长之后,所有更长的候选都已经失败,因此新的 给出最长的匹配前缀。如果其长度为 ,已读文本就以完整模式串结尾,这证明报告的匹配确实存在。为了继续扫描,既是该次匹配后缀又较短的最长模式串前缀,恰好是模式串的最长真边界,其长度为 。
这样就恢复了处理字符之间的不变量,报告一次匹配之后也一样。每个可能的匹配终点都会被检查,所以不会遗漏任何出现。重置保留了可能开始一次重叠匹配的后缀。
证明透视
边界引理在两处发挥作用
同一个引理让不变量通过两种不同的动作。失配时,回退 沿着已匹配字符串 P[:j] 的边界往下走,这些恰好就是较短的候选状态,所以没有状态被跳过。完整匹配之后,已读的字符串就是整个模式串,其最长真边界的长度是 ;重置为此值,会保留可能开始下一个出现位置的最长后缀,重置为零则会把它丢掉。每次回退之后,同一个文本字符会再被比较,所以候选状态被淘汰,只是因为它的下一个字符失配,绝不是因为它的长度小。
例题 9.1.6
(重叠匹配需要保留边界)
在 aaaaa 中搜索 aaa。模式串的前缀表为 [0, 1, 2]。在文本下标 2 处,一个从 0 开始的完整匹配结束。将 重置为 :最后两个字符已经匹配 aa。
下一个 a 完成从 1 开始的另一次匹配。同样的重置使最后一个 a 完成从 2 开始的匹配。输出为 [0, 1, 2]。若在第一次匹配后重置为零,就会丢失这些重叠的起点。
类似地,aba 在 ababa 中出现的位置为 [0, 2]。它的末尾边界 a 将一次匹配末尾的信息带入下一次匹配。
随意减一可能产生错误匹配
反例模式
用 j 减一代替回退会破坏不变量
取模式串 ababc 和文本 ababbc。读完前四个字符 abab 后,匹配长度为 4。下一个文本字符是 b,与预期的 c 失配。
错误地回退到长度 3,相当于声称 aba 是已读文本 abab 的后缀,而它实际的长度为三的后缀是 bab。当前的 b 随后会与模式串下标 3 处的字符匹配,而最后的 c 看起来会完成一次完整匹配。错误算法报告起点 1,但该文本窗口是 babbc,并非 ababc。
正确的回退为 ;这两个状态都无法由当前的 b 延长。算法不会报告任何匹配。回退的依据是子串相等,而不只是下标在数值上变小。
这个交互图重现下面练习题的方法,包括上面的错误匹配例子。若想独立练习,请先尝试题目。选择错误匹配示例、搜索视图及递减规则,可查看无效回退。
计算总工作量,而非单个字符的工作量
一个字符可能触发多次回退,但这并不意味着整个算法需要二次时间。
定理 9.1.7
(KMP 的总工作量是线性的)
在符号比较为常数时间的假设下,前缀预处理需时 ,文本扫描需时 ,所以搜索总时间为 ,再加上输出 个匹配的 。
证明
(以增长额度抵消每次下降)
在构造前缀函数时,当前匹配长度每次外层迭代至多增加一。每次回退都使它至少减少一,而且它永远不会变成负数。从零开始,回退迭代的总次数不能超过增长的总量,而增长总量至多为模式串长度。
文本扫描的均摊计数相同。每个文本字符至多使 增加一次。失配回退和完整匹配后的重置只会使它减少。因此,在整个文本扫描过程中,失配循环的总迭代次数至多是线性的。除此之外,每次外层迭代只进行常数次比较。
假设比较两个符号需要常数时间,预处理耗时 ,搜索耗时 。返回 个匹配需要额外的 输出工作和存储。前缀表使用 工作空间;匹配列表是额外的输出空间。包括空模式串的情况在内,起点至多有 个,所以总时间为 。
证明透视
为每次回退付款的势能
把 当作势能。它从 开始、永不为负,每次外层迭代至多增加 。回退把 换成 ,而 ,因为真边界比它所在的字符串短,所以每次回退至少使 减少 。因此回退次数至多等于总增长量:扫描中至多 次,预处理中至多 次。这个界是均摊的:单个字符可能触发许多次回退,但那是在先前的字符把 推到那么高之后。
常见错误
(线性时间不等于每个字符只比较一次)
这一论证并不是说每个文本字符只比较一次。文本下标从不后退,但当前字符可能与模式串的多个位置比较。使搜索保持线性的是总次数的界。
包含空模式串的完整实现
我们约定空模式串在文本的每个边界处都出现,包括第一个字符之前和最后一个字符之后。因此共有 个位置。单独处理这一情况可避免访问空模式串的下标。
def prefix_function(pattern):
pi = [0] * len(pattern)
for i in range(1, len(pattern)):
j = pi[i - 1]
while j > 0 and pattern[i] != pattern[j]:
j = pi[j - 1]
if pattern[i] == pattern[j]:
j += 1
pi[i] = j
return pi
def kmp_find_all(text, pattern):
if not pattern:
return list(range(len(text) + 1))
pi = prefix_function(pattern)
matches = []
j = 0
for i, symbol in enumerate(text):
while j > 0 and symbol != pattern[j]:
j = pi[j - 1]
if symbol == pattern[j]:
j += 1
if j == len(pattern):
matches.append(i - len(pattern) + 1)
j = pi[j - 1]
return matches
完整匹配检查会在下一次迭代之前重置 ,因此比较时 pattern[j] 始终没有越界。如果模式串比文本长,扫描自然不可能达到完整长度。这里不需要特殊的分隔符,也不需要把模式串与文本拼接起来。
常见错误
(用 而不是 回退)
在状态 失配后,已匹配的字符串是 P[:j],其最长真边界的长度是 。 属于较长的前缀 P[:j+1],而它包含刚刚失配的字符。对模式串 ababc 和文本 abababc,正确的扫描在读入 abab 后到达 ,遇到 a 失配,回退到 ,并报告位置 的出现。若用 ,就丢掉边界 ab,漏掉这个出现。
最长边界还能揭示最小周期
定义 9.1.8
(字符串的周期)
对于长度为 的非空字符串 ,如果正整数 满足对每个 都有 ,则称 为一个周期。长度为 的边界恰好表示前 个字符等于后 个字符,这正是 时的周期条件。
定理 9.1.9
(由最长边界得出最小周期)
对长度为 的非空字符串 , 的最小正周期为
证明
(周期与边界一一对应)
由上述对应, 本身就是一个周期。任何其他周期 都给出长度为 的边界,而这个长度不超过最长边界的长度,所以 。
周期不一定整除字符串长度。ababa 的周期为 2,尽管长度为 5。如果周期整除 ,该字符串就由其开头长度为一个周期的块完整重复而成;例如 ababab 将 ab 重复了三次。
例题 9.1.10
(最小周期,包括没有边界的字符串)
对 abcabcab,前缀表为 ,故 ,:这个字符串是块 abc 的重复,并以不完整的块 ab 结尾。对 abc,表为 ,:它没有非空的真边界,所以唯一的周期就是整个字符串的长度。对 aaaa,表为 ,。
练习与详细解答
快速检查
(1. 识别真正的真边界)
列出 ababa 的所有真边界长度,包括零。为什么排除长度 2、4 和 5?
解答 · 解答 1
长度为 0、1 和 3。对应的非空字符串是 a 和 aba。长度为二的前缀 ab 不等于后缀 ba;长度为四的前缀 abab 不等于后缀 baba。长度五被排除,因为真边界不能是整个字符串。
快速检查
(2. 沿实际的边界链接回退)
对于 ababaca,处理 c 之前当前匹配的边界是什么?写出回退长度及该下标处最终的前缀函数值。
解答 · 解答 2
前一个前缀 ababa 的最长边界是长度为 3 的 aba。回退链为 。字符 c 无法延长这些状态中的任何一个,因此 。
快速检查
(3. 保留重叠起点)
在 aaaaa 中找到第一个 aaa 之后,保留什么状态,为什么?写出所有匹配位置。如果把状态重置为零会怎样?
解答 · 解答 3
保留状态 2,即边界 aa 的长度。匹配位置为 0、1 和 2。重置为零会丢弃已经匹配的两个后缀字符,因此在这种错误扫描中,剩余文本无法揭示那两个长度为三的重叠出现。
快速检查
(4. 判断错误的回退状态)
在 ababc 与 ababbc 的反例中,第一次失配后为什么长度 3 不是有效状态?错误算法最终会报告哪个文本窗口?
解答 · 解答 4
已读的 abab 以 bab 而非模式串前缀 aba 结尾,因此长度 3 并不描述真实的后缀匹配。错误延长之后,算法报告起点 1 处的窗口 babbc。其内容不相等,表明这是误报,而不仅仅是搜索效率低。
快速检查
(5. 解释反复失败时总比较次数仍为线性)
假设一个文本字符触发了多次回退循环迭代。什么量在下降?此前的哪些工作限制了整个扫描中这类迭代的总次数?
解答 · 解答 5
匹配前缀长度 在每次回退时严格下降。它从零开始,永不为负,并且每个文本字符至多使它增长一次。因此,总下降量只能由先前增长提供的线性预算支付。每个文本字符额外只需常数次比较,使总搜索时间保持线性。
快速检查
(6. 求周期时不假设整除)
用最长边界公式求 ababab 和 ababa 的最小周期。哪个字符串由整数个 ab 块组成?为什么另一个按照定义仍有周期?
解答 · 解答 6
它们的最长边界长度分别为 4 和 3,所以最小周期都是 2。ababab 长度为六,由三个 ab 组成。ababa 长度为五,但下标至少为二的每个字符仍等于其前面两个位置的字符。周期条件允许最后一个块不完整。