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

用最长相等前后缀保存失配信息,让文本指针只向前走。

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

KMPKnuth–Morris–Pratt

失配时利用前缀函数保留已匹配信息,实现 O(n+m) 模式匹配。

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

本课要建立的能力

用最长相等前后缀保存失配信息,让文本指针只向前走。

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

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文本位置不回退
读完 acaj 达到 7,起点 2完整命中

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

回退的是模式的已匹配长度,不是已经读过的文本位置。

04为什么这个方法成立

  1. 失配后任何可能保留的部分必须同时为已匹配串后缀与模式前缀。
  2. pi 链按长度递减枚举所有可行边界,不会漏掉可能匹配。
  3. 文本每次向前,匹配长度总增长受文本长度限制,因此回退总次数也为线性。

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从手算到独立迁移

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

练习 1 · 复现与理解

aaaa 中 aa 的全部起点?

需要一点提示

允许重叠。

查看解析与答案

[0,1,2]。

练习 2 · 边界与辨析

pi[0] 为什么是 0?

需要一点提示

真前缀不能等于整个串。

查看解析与答案

单字符没有非空真前缀。

练习 3 · 变式与迁移

怎样判断字符串是否由较短片段重复组成?

需要一点提示

最后一个边界给出候选周期。

查看解析与答案

令 k=n−pi[n−1],若 k<n 且 n%k==0,则由长度 k 的前缀重复组成。

继续深入这个专题

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

Princeton · 字符串算法

理解之后,继续递进

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