KMP 字符串匹配

KMP（Knuth-Morris-Pratt）算法用来查找模式串 P 在文本串 T 中的所有出现位置。通过利用匹配失败时的部分匹配信息，避免暴力的重复，将最坏时间复杂度从  降至 。

暴力匹配

暴力匹配思想：从文本串的每个位置开始，逐个字符与模式串比较，一旦失配就移动一位重新开始。导致大量回溯：如 T = "aaaaaaaaab", P = "aaab"，每次失配后模式串只能右移一位，之前比较过的字符被反复比较。

KMP 算法思维：利用已经匹配成功的部分，跳过一些不可能匹配的位置。

前缀函数

π 函数 / next 数组

预处理模式串 P，计算一个前缀函数数组，常记为 next 或 pi。

定义：对于模式串 P 的前缀 P[0..i]（长度为 i+1），定义 next[i] 为该前缀的最长真前缀（不包含整个串）等于真后缀的长度。

例如：P = "ababaca"

• i=0, "a" → 没有真前后缀 → next[0]=0
• i=1, "ab" → 真前缀 "a", 真后缀 "b" → 无相等 → next[1]=0
• i=2, "aba" → 真前缀 "a","ab"; 真后缀 "a","ba" → 最长相等为 "a" → 长度 1 → next[2]=1
• i=3, "abab" → 真前缀 "a","ab","aba"; 真后缀 "b","ab","bab" → 最长相等 "ab" → 长度2 → next[3]=2
• i=4, "ababa" → 最长相等 "aba" → 长度3 → next[4]=3
• i=5, "ababac" → 无相等 → next[5]=0
• i=6, "ababaca" → 最长相等 "a" → 长度1 → next[6]=1

直观理解：next[i] 表示当模式串在位置 i 发生失配时，可安全将模式串的指针回退继续比较，从而避免从头开始。

计算 next 数组

使用递推时间复杂度 O(m)：

nxt = [0] * mj = 0# 当前已匹配的前缀长度for i in range(1, m):while j > 0and p[i] != p[j]:        j = nxt[j-1]   # 回退到之前的匹配位置if p[i] == p[j]:        j += 1    nxt[i] = j

手推（P = "ababaca"）：

• i=1, p[1]='b', j=0，p[1]!=p[0] 且 j==0 → 不进入 while，j 不变 → nxt[1]=0
• i=2, p[2]='a', j=0，p[2]==p[0] → j=1 → nxt[2]=1
• i=3, p[3]='b', j=1，p[3]==p[1] → j=2 → nxt[3]=2
• i=4, p[4]='a', j=2，p[4]==p[2] → j=3 → nxt[4]=3
• i=5, p[5]='c', j=3，p[5]!=p[3] → while: j = nxt[2]=1，p[5]!=p[1] → j = nxt[0]=0 → p[5]!=p[0] → j=0 → nxt[5]=0
• i=6, p[6]='a', j=0，p[6]==p[0] → j=1 → nxt[6]=1

nxt = [0,0,1,2,3,0,1]，与定义一致。

匹配过程

根据 next 数组，扫描文本串 s，维护当前匹配的模式串指针 j。

res = []j = 0for i in range(n):          # i 是文本串索引while j > 0and s[i] != p[j]:        j = nxt[j-1]        # 回退模式串指针if s[i] == p[j]:        j += 1if j == m:              # 找到一个完整匹配        res.append(i - m + 1)  # 起始位置        j = nxt[j-1]        # 继续寻找下一个匹配（允许重叠）

关键：

• 文本串指针 i 从不回退，扫描一遍文本串。
• 当字符相等时，j 前进；失配则利用 next 将 j 回退到某个合适位置，而不回退到 0。
• 当 j == m 时，匹配成功，记录起始位置， j 回退到 nxt[m-1] 以允许重叠匹配。

题例

T = "ababaababac"P = "ababac"print(kmp_search(T, P))  # 输出: [5]

手动验证："ababaababac" 中从索引5开始 "ababac" 匹配。

复杂度分析

• 构建 next 数组：O(m)，每个字符最多被比较两次。
• 匹配过程：O(n)，文本串的每个字符最多被比较两次。
• 总时间复杂度：O(n + m)，空间复杂度：O(m) 用于 next 数组。

KMP 的优化与变种

• nextval 数组：在构建 next 时，若 P[i] == P[next[i]]，则继续递归回退，可避免匹配失败后的重复比较。
• 统计匹配次数：在 j == m 时不停止，继续用 j = nxt[j-1] 寻找下一个匹配。
• 求模式串在文本串中出现的所有位置。

算法竞赛应用场景

• 字符串匹配统计：查找子串出现的次数/位置。
• 循环节问题：若字符串长度为 len，且 len % (len - next[-1]) == 0，则最小循环节长度为 len - next[-1]。
• 前缀与后缀最长的公共部分：利用 next 数组的性质。
• 字符串周期：KMP 的 next 数组可以直接求出字符串的最小周期。

标准库的 find 和 in

Python 内置的字符串查找find, index使用优化的混合算法（Boyer-Moore 和 Horspool），在实际使用中通常比手写 KMP 更快，因为其底层用 C 实现。

• 典例：洛谷 P3375（KMP 模板题）、LeetCode 28

KMP 的关键在于理解 next 数组的含义和递推过程。建议手动模拟几个字符串的计算，并调试跟踪匹配时的指针变化。一旦搞懂了前缀函数的思想，KMP 便很好做。