KMP 算法（Knuth-Morris-Pratt）专业讲解

一、问题定义

字符串匹配问题（String Matching / Pattern Matching）：

KMP 算法由 Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年联合发表，是第一个线性时间的字符串匹配算法。

---

二、核心思想

朴素算法的瓶颈

KMP 的关键洞察

---

三、前缀函数（Prefix Function）/ next 数组

3.1 形式化定义

"真"（proper）意味着 $k < i+1$，即前后缀不能是字符串本身。

3.2 示例

			最长相等真前后缀
0	a	0	无
1	ab	0	无
2	aba	1	a
3	abab	2	ab
4	ababa	3	aba
5	ababac	0	无
6	ababaca	1	a

3.3 构建算法

def compute_prefix_function(P):
    m = len(P)
    pi = [0] * m
    k = 0  # 当前最长相等真前后缀的长度
    for q in range(1, m):
        while k > 0 and P[q] != P[k]:
            k = pi[k - 1]  # 回退：利用已计算的前缀函数值
        if P[q] == P[k]:
            k += 1
        pi[q] = k
    return pi

关键理解：while 循环中的 k = pi[k-1] 是算法的精髓——当前后缀不匹配时，不是简单地令 $k=0$，而是退到次长的相等真前后缀继续尝试。这保证了不遗漏任何可能的匹配。

3.4 构建过程的正确性（归纳论证）

• 基础：$\pi[0] = 0$（单字符无真前后缀）。
• • 若 $P[q] = P[k]$，则 $\pi[q] = k + 1$（直接扩展）。

---

四、匹配过程

def kmp_search(T, P):
    n, m = len(T), len(P)
    pi = compute_prefix_function(P)
    q = 0  # 当前已匹配的字符数（即模式串指针）
    results = []
    
    for i in range(n):  # 主串指针 i 单调递增，永不回退
        while q > 0 and T[i] != P[q]:
            q = pi[q - 1]  # 模式串指针跳转
        if T[i] == P[q]:
            q += 1
        if q == m:
            results.append(i - m + 1)  # 记录匹配位置
            q = pi[q - 1]  # 继续寻找下一个匹配（重叠匹配）
    
    return results

匹配过程图解

状态1: i=0..5, q=6
  T: a b a b a b a b c a
  P: a b a b a c a
                   ↑ T[5]='b' ≠ P[5]='c'，失配！
  q = pi[4] = 3，跳转到 P[3]

状态2: i=5, q=3
  T: a b a b a b a b c a
  P:       a b a b a c a
                   ↑ T[5]='b' ≠ P[3]='b'？不，相等！q=4

状态3: i=6, q=4
  T: a b a b a b a b c a
  P:       a b a b a c a
                     ↑ T[6]='a' ≠ P[4]='a'？相等！q=5

状态4: i=7, q=5
  T: a b a b a b a b c a
  P:       a b a b a c a
                       ↑ T[7]='b' ≠ P[5]='c'，失配！
  q = pi[4] = 3 ...（继续）

---

五、复杂度分析

证明思路（摊还分析）：

• 前缀函数构建同理：$O(m)$。

总计：$O(n) + O(m) = O(n + m)$。

六、next 数组的两种常见变体

变体	定义	失配时操作	常见于
		q = pi[q-1]	CLRS、算法竞赛
next 数组（右移一位）		j = next[j]	国内教材（严蔚敏版）

两者本质相同，只是下标约定不同。国内教材中常见的 next[0] = -1 写法是为了避免边界判断。

---

七、KMP 的扩展与应用

应用	说明
多模式匹配	Aho-Corasick 算法（AC 自动机）是 KMP 的多模式推广
周期检测
最短循环节	利用前缀函数求字符串的最小重复单元
字符串压缩	基于周期的 Run-Length 编码
回文检测
Z 函数（扩展 KMP）

---

八、与其他线性匹配算法的对比

算法	时间	空间	特点
KMP			主串指针不回退，适合流式输入
Rabin-Karp			基于哈希，支持多模式匹配
Boyer-Moore	最坏 $O(nm)$，实践中亚线性		从右向左比较，跳跃距离大，实践中最快
Sunday			BM 的简化版，关注主串中下一个字符
Z 算法

---

九、一句话总结

KMP 算法的本质是：通过预处理模式串的自相似结构（前缀函数），将失配时的"盲目回退"转化为"精准跳转"，从而保证主串指针单调前进，实现线性时间