KMP 算法（Knuth-Morris-Pratt 算法）

字数 2165 2025-10-27 22:12:31

KMP 算法（Knuth-Morris-Pratt 算法）

题目描述
KMP 算法用于解决字符串匹配问题：给定一个文本串 text 和一个模式串 pattern，请在 text 中找出 pattern 出现的所有位置。例如，text = "ABABDABACDABABC"，pattern = "ABABC"，应返回匹配的起始位置。目标是实现一个时间复杂度为 O(n + m) 的高效算法，其中 n 和 m 分别是文本串和模式串的长度。

解题过程循序渐进讲解

第一步：理解暴力匹配的缺点
暴力匹配的做法是：从文本串的每个字符开始，逐个与模式串比较，若出现不匹配，则文本串的指针回退到本次匹配起始位置的下一个字符，模式串指针回退到开头。
缺点：当出现不匹配时，文本串和模式串的指针都发生回退，导致时间复杂度为 O(n*m)。
例如：

text:    "AAAAAB"  
pattern: "AAAB"

在最后一次字符 'A' 和 'B' 不匹配时，暴力匹配会让文本串回退到第二个字符重新开始，效率低下。

第二步：KMP 的核心思想——利用已匹配信息
KMP 算法的核心是：当出现不匹配时，文本串的指针不回退，只移动模式串的指针到一个特定位置，继续比较。
这需要预先对模式串进行分析，构建一个 部分匹配表（Partial Match Table），通常称为 next 数组。

第三步：理解最长公共前后缀（LPS）

前缀：指除了最后一个字符以外，字符串的所有头部组合。
后缀：指除了第一个字符以外，字符串的所有尾部组合。
最长公共前后缀：对于模式串的每个子串 pattern[0:i]，找出其最长的相等前缀和后缀的长度（这个长度必须小于子串长度）。

示例：模式串 "ABABC"

子串 "A"：无公共前后缀 → 长度 0
子串 "AB"：前缀 ["A"]，后缀 ["B"]，无公共 → 长度 0
子串 "ABA"：前缀 ["A","AB"]，后缀 ["A","BA"]，公共最长是 "A" → 长度 1
子串 "ABAB"：前缀 ["A","AB","ABA"]，后缀 ["B","AB","BAB"]，公共最长是 "AB" → 长度 2
子串 "ABABC"：前缀 ["A","AB","ABA","ABAB"]，后缀 ["C","BC","ABC","BABC"]，无公共 → 长度 0

因此，LPS 数组为 [0, 0, 1, 2, 0]。

第四步：构建 next 数组
next 数组的定义是：对于每个位置 i，当模式串的第 i 个字符与文本串不匹配时，模式串应该跳转到 next[i] 的位置继续比较。
通常 next[i] 表示的是 子串 pattern[0:i-1] 的最长公共前后缀长度（即 LPS 的值）。
但实际实现中，next 数组有多种定义方式，这里采用一种常见形式：

next[0] = -1（表示模式串第一个字符就不匹配时，文本串指针右移）
next[i] = LPS[i-1]（即上述 LPS 数组右移一位，开头补 -1）

对于 "ABABC"：
LPS: [0, 0, 1, 2, 0]
next: [-1, 0, 0, 1, 2]

第五步：KMP 匹配过程

初始化两个指针 i（文本串）和 j（模式串），均从 0 开始。
循环比较 text[i] 和 pattern[j]：
- 若 j == -1，说明模式串已无法回退，则 i++，j=0（相当于模式串从头开始）
- 若 text[i] == pattern[j]，则 i++，j++
- 若 text[i] != pattern[j]，则 j = next[j]（模式串指针回退到 next[j] 位置）
当 j 等于模式串长度时，表示匹配成功，记录位置 i - j，然后令 j = next[j] 继续寻找下一个匹配。

示例：

text:    "ABABDABACDABABC"  
pattern: "ABABC"  
next:    [-1, 0, 0, 1, 2]

匹配过程：

i=0,j=0: A=A → i=1,j=1
i=1,j=1: B=B → i=2,j=2
i=2,j=2: A=A → i=3,j=3
i=3,j=3: B=B → i=4,j=4
i=4,j=4: D!=C → j=next[4]=2
i=4,j=2: D!=A → j=next[2]=0
i=4,j=0: D!=A → j=next[0]=-1
i=4,j=-1 → i=5,j=0
...（继续匹配，最终在 i=10 时匹配到 "ABABC"）

第六步：代码实现要点
构建 next 数组的过程也是一个“模式串自我匹配”的过程，采用类似 KMP 的方法：

初始化 next[0]=-1, k=-1, j=0
循环 j 从 0 到 len-2：
- 若 k==-1 或 pattern[j]==pattern[k]，则 k++, j++, next[j]=k
- 否则 k=next[k]

匹配过程如上所述。

总结
KMP 算法通过预处理模式串得到 next 数组，在匹配失败时利用已匹配信息避免文本串指针回退，将时间复杂度优化到 O(n+m)。关键在于理解最长公共前后缀和 next 数组的构建与使用。

KMP 算法（Knuth-Morris-Pratt 算法）题目描述 KMP 算法用于解决字符串匹配问题：给定一个文本串 text 和一个模式串 pattern ，请在 text 中找出 pattern 出现的所有位置。例如， text = "ABABDABACDABABC" ， pattern = "ABABC" ，应返回匹配的起始位置。目标是实现一个时间复杂度为 O(n + m) 的高效算法，其中 n 和 m 分别是文本串和模式串的长度。解题过程循序渐进讲解第一步：理解暴力匹配的缺点暴力匹配的做法是：从文本串的每个字符开始，逐个与模式串比较，若出现不匹配，则文本串的指针回退到本次匹配起始位置的下一个字符，模式串指针回退到开头。缺点：当出现不匹配时，文本串和模式串的指针都发生回退，导致时间复杂度为 O(n* m)。例如：在最后一次字符 'A' 和 'B' 不匹配时，暴力匹配会让文本串回退到第二个字符重新开始，效率低下。第二步：KMP 的核心思想——利用已匹配信息 KMP 算法的核心是：当出现不匹配时，文本串的指针不回退，只移动模式串的指针到一个特定位置，继续比较。这需要预先对模式串进行分析，构建一个部分匹配表（Partial Match Table），通常称为 next 数组。第三步：理解最长公共前后缀（LPS）前缀：指除了最后一个字符以外，字符串的所有头部组合。后缀：指除了第一个字符以外，字符串的所有尾部组合。最长公共前后缀：对于模式串的每个子串 pattern[0:i] ，找出其最长的相等前缀和后缀的长度（这个长度必须小于子串长度）。示例：模式串 "ABABC" 子串 "A"：无公共前后缀 → 长度 0 子串 "AB"：前缀 [ "A"]，后缀 [ "B" ]，无公共 → 长度 0 子串 "ABA"：前缀 [ "A","AB"]，后缀 [ "A","BA" ]，公共最长是 "A" → 长度 1 子串 "ABAB"：前缀 [ "A","AB","ABA"]，后缀 [ "B","AB","BAB" ]，公共最长是 "AB" → 长度 2 子串 "ABABC"：前缀 [ "A","AB","ABA","ABAB"]，后缀 [ "C","BC","ABC","BABC" ]，无公共 → 长度 0 因此，LPS 数组为 [0, 0, 1, 2, 0] 。第四步：构建 next 数组 next 数组的定义是：对于每个位置 i，当模式串的第 i 个字符与文本串不匹配时，模式串应该跳转到 next[ i ] 的位置继续比较。通常 next[ i] 表示的是子串 pattern[ 0:i-1] 的最长公共前后缀长度（即 LPS 的值）。但实际实现中，next 数组有多种定义方式，这里采用一种常见形式： next[ 0 ] = -1（表示模式串第一个字符就不匹配时，文本串指针右移） next[ i] = LPS[ i-1 ]（即上述 LPS 数组右移一位，开头补 -1）对于 "ABABC" ： LPS: [0, 0, 1, 2, 0] next: [-1, 0, 0, 1, 2] 第五步：KMP 匹配过程初始化两个指针 i（文本串）和 j（模式串），均从 0 开始。循环比较 text[ i] 和 pattern[ j ]：若 j == -1，说明模式串已无法回退，则 i++，j=0（相当于模式串从头开始）若 text[ i] == pattern[ j ]，则 i++，j++ 若 text[ i] != pattern[ j]，则 j = next[ j]（模式串指针回退到 next[ j ] 位置）当 j 等于模式串长度时，表示匹配成功，记录位置 i - j，然后令 j = next[ j ] 继续寻找下一个匹配。示例：匹配过程： i=0,j=0: A=A → i=1,j=1 i=1,j=1: B=B → i=2,j=2 i=2,j=2: A=A → i=3,j=3 i=3,j=3: B=B → i=4,j=4 i=4,j=4: D!=C → j=next[ 4 ]=2 i=4,j=2: D!=A → j=next[ 2 ]=0 i=4,j=0: D!=A → j=next[ 0 ]=-1 i=4,j=-1 → i=5,j=0 ...（继续匹配，最终在 i=10 时匹配到 "ABABC"）第六步：代码实现要点构建 next 数组的过程也是一个“模式串自我匹配”的过程，采用类似 KMP 的方法：初始化 next[ 0 ]=-1, k=-1, j=0 循环 j 从 0 到 len-2：若 k==-1 或 pattern[ j]==pattern[ k]，则 k++, j++, next[ j ]=k 否则 k=next[ k ] 匹配过程如上所述。总结 KMP 算法通过预处理模式串得到 next 数组，在匹配失败时利用已匹配信息避免文本串指针回退，将时间复杂度优化到 O(n+m)。关键在于理解最长公共前后缀和 next 数组的构建与使用。