01先把问题说具体
在文本 'abababaca' 中找模式 'ababaca'。前面匹配很多字符后失配,为什么不必从下一个起点全部重比?
02一步步得到方法
前缀函数记录可复用的边界
pi[i] 是模式前缀 p[0:i+1] 的最长真前缀与后缀相等的长度,真前缀不能是整个串。例如 ababa 的最长相同前后缀为 aba,长度 3。
文本已匹配 j 个字符后遇到失配,后面仍可能成为模式开头的部分,必须是这段已匹配前缀的后缀。因此候选长度跳到 pi[j−1],而不是将 j 减 1 或将文本指针回退。
构造 pi 本身也复用相同思想
计算 pi[i] 时,从上一位置的边界长度 j=pi[i−1] 尝试延长;若新字符不匹配,沿更短边界链回退;匹配则 j+1。
找到完整模式后,继续用 pi[j−1] 接着搜索可保留重叠匹配。例如文本 aaaa、模式 aa 应返回 0、1、2,而不是只找互不重叠的两次。
失配时保留已匹配后缀的信息
已匹配的模式前缀中,如果某个后缀同时也是模式前缀,那么失配后它可能继续作为新的已匹配开头。前缀函数记录最长这样的边界,使文本指针无需回退。
回退 j=pi[j−1] 可能多次发生,但每次都降低 j,而成功匹配才增加 j,总增加和总降低都受扫描长度限制。这解释了线性复杂度,而不只是看到嵌套 while 就猜二次。
03把一个小例子完全算清楚
p='ababaca',pi=[0,0,1,2,3,0,1];text='abababaca'。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 前五字符 | 已匹配 ababa,j=5 | 准备匹配模式中的 c |
| 文本第 5 位 b | 失配,j 从 5 跳到 pi[4]=3 | 已匹配后缀 aba 可复用 |
| 继续比较 b | 模式第 3 位 b 相等,j=4 | 文本位置不回退 |
| 读完 aca | j 达到 7,起点 2 | 完整命中 |
窄屏可左右滑动表格,阅读完整计算与理由。
回退的是模式的已匹配长度,不是已经读过的文本位置。
04为什么这个方法成立
- 失配后任何可能保留的部分必须同时为已匹配串后缀与模式前缀。
- pi 链按长度递减枚举所有可行边界,不会漏掉可能匹配。
- 文本每次向前,匹配长度总增长受文本长度限制,因此回退总次数也为线性。
05把推导翻译成代码
Python · 可独立运行的教学实现
def prefix_function(p):
pi = [0]*len(p)
for i in range(1,len(p)):
j = pi[i-1]
while j and p[i] != p[j]:
j = pi[j-1]
if p[i] == p[j]:
j += 1
pi[i] = j
return pi
def kmp(text,pattern):
if not pattern:
return list(range(len(text)+1))
pi, j, result = prefix_function(pattern), 0, []
for i,c in enumerate(text):
while j and c != pattern[j]:
j = pi[j-1]
if c == pattern[j]:
j += 1
if j == len(pattern):
result.append(i-j+1)
j = pi[j-1]
return result逐个理解关键决定
j = pi[j-1]- 跳到下一个可行边界,不是任意缩短。
j = pi[j-1]- 完整命中后仍保留最长边界,继续寻找重叠匹配。
06时间、空间与实现范围
模式长度 m,文本长度 n,预处理 O(m)、扫描 O(n),空间 O(m) 加输出。
按码点相等匹配,不自动做大小写或 Unicode 规范化;空模式约定匹配所有 n+1 个间隙。
07改变条件,检查哪里会出错
失配后把文本指针也退回
会恢复重复比较,丢失 KMP 的线性优势。
完整命中后把 j 永远清成0
寻找重叠匹配时应保留正确的边界状态,否则像 aaa 中的 aa 会漏掉第二个匹配。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
aaaa 中 aa 的全部起点?
需要一点提示
允许重叠。
查看解析与答案
[0,1,2]。
pi[0] 为什么是 0?
需要一点提示
真前缀不能等于整个串。
查看解析与答案
单字符没有非空真前缀。
怎样判断字符串是否由较短片段重复组成?
需要一点提示
最后一个边界给出候选周期。
查看解析与答案
令 k=n−pi[n−1],若 k<n 且 n%k==0,则由长度 k 的前缀重复组成。