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

字数 2348 2025-10-27 21:56:23

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

KMP 算法是一种高效的字符串匹配算法，用于在一个主文本字符串（text）中查找一个模式字符串（pattern）的出现位置。其核心思想是当出现不匹配时，利用已经匹配的部分信息，避免从头重新开始比较，从而将时间复杂度优化到 O(n + m)，其中 n 是文本长度，m 是模式长度。

问题描述
给定一个文本字符串 text 和一个模式字符串 pattern，请找出 pattern 在 text 中所有出现的起始索引。

示例
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
应返回匹配的起始索引（例如，从 0 开始计数，可能返回 [10]）。

解题步骤

理解暴力匹配的不足
- 暴力匹配：从 text 的每个位置开始，逐个字符与 pattern 比较。若不匹配，则 text 的指针回退到本次匹配起始位置的下一个字符，pattern 的指针回退到开头。
- 缺点：效率低，最坏情况 O(n*m)。例如 text = "AAAAAAB"，pattern = "AAAB"，每次匹配失败后，text 指针只前进一位，重复比较很多次。
KMP 的核心思想：利用部分匹配信息
- 当 pattern 与 text 在某个位置不匹配时，暴力法会将 pattern 向后移动一位重新比较。KMP 算法通过预处理 pattern，生成一个“部分匹配表”（通常称为 next 数组），利用已匹配的前缀信息，将 pattern 一次移动多位，避免 text 指针回退。
部分匹配表（next 数组）
- 定义：对于 pattern 的前缀子串 pattern[0:i]，其“最长相等前后缀”的长度（不包括自身）即为 next[i] 的值。
  - 前缀：指不包括最后一个字符的所有连续子串。
  - 后缀：指不包括第一个字符的所有连续子串。
  - "最长相等前后缀"：即前缀和后缀中相同的部分的最大长度。
- 示例：pattern = "ABABCABAB"
  - 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: "ABABC"，前缀 {"A","AB","ABA","ABAB"}，后缀 {"C","BC","ABC","BABC"}，无相同，next[4] = 0。
  - 继续计算得 next = [0, 0, 1, 2, 0, 1, 2, 3, 4]。
构建 next 数组的步骤
- 初始化：next[0] = 0，i = 1（当前子串末尾），j = 0（已匹配的前缀长度）。
- 遍历 i 从 1 到 m-1：
  - 若 pattern[i] == pattern[j]，则 j++，next[i] = j，i++。
  - 若不等且 j > 0，则 j = next[j-1]（回退到前一个前缀的匹配位置）。
  - 若 j=0 且不匹配，则 next[i] = 0，i++。
- 示例（pattern="ABABCABAB"）：
  - i=1, j=0: 'B' != 'A'，j=0 → next[1]=0, i=2。
  - i=2, j=0: 'A' == 'A' → j=1, next[2]=1, i=3。
  - i=3, j=1: 'B' == 'B' → j=2, next[3]=2, i=4。
  - i=4, j=2: 'C' != 'A'，j>0 → j=next[1]=0。
    - 现在 j=0, 'C' != 'A' → next[4]=0, i=5。
  - 继续过程，得到 next = [0,0,1,2,0,1,2,3,4]。
使用 next 数组进行匹配
- 初始化：i=0（text 指针），j=0（pattern 指针）。
- 遍历 i 从 0 到 n-1：
  - 若 text[i] == pattern[j]，则 i++, j++。
  - 若 j == m，表示完全匹配，记录位置 i-m，然后 j = next[j-1]（继续寻找下一个匹配）。
  - 若字符不匹配：
    - 若 j > 0，则 j = next[j-1]（pattern 向右移动，i 不变）。
    - 若 j=0，则 i++（pattern 开头就不匹配，text 指针前进）。
- 示例（text="ABABDABACDABABCABAB", pattern="ABABCABAB"）：
  - 初始 i=0,j=0：匹配到 i=4,j=4时，text[4]='D' != pattern[4]='C'。
  - j=4>0 → j=next[3]=2（pattern 移动，比较 text[4] 与 pattern[2]）。
  - text[4]='D' != pattern[2]='A'，j=2>0 → j=next[1]=0。
  - j=0，i++ → i=5，重新开始匹配... 直到在 i=10 处找到完整匹配。

总结
KMP 算法通过预处理 pattern 得到 next 数组，在匹配失败时智能移动 pattern，确保 text 指针不回溯，实现高效匹配。关键点在于理解最长相等前后缀的概念及 next 数组的构建与使用。

KMP 算法（Knuth-Morris-Pratt 算法） KMP 算法是一种高效的字符串匹配算法，用于在一个主文本字符串（text）中查找一个模式字符串（pattern）的出现位置。其核心思想是当出现不匹配时，利用已经匹配的部分信息，避免从头重新开始比较，从而将时间复杂度优化到 O(n + m)，其中 n 是文本长度，m 是模式长度。问题描述给定一个文本字符串 text 和一个模式字符串 pattern，请找出 pattern 在 text 中所有出现的起始索引。示例 text = "ABABDABACDABABCABAB" pattern = "ABABCABAB" 应返回匹配的起始索引（例如，从 0 开始计数，可能返回 [ 10 ]）。解题步骤理解暴力匹配的不足暴力匹配：从 text 的每个位置开始，逐个字符与 pattern 比较。若不匹配，则 text 的指针回退到本次匹配起始位置的下一个字符，pattern 的指针回退到开头。缺点：效率低，最坏情况 O(n* m)。例如 text = "AAAAAAB"，pattern = "AAAB"，每次匹配失败后，text 指针只前进一位，重复比较很多次。 KMP 的核心思想：利用部分匹配信息当 pattern 与 text 在某个位置不匹配时，暴力法会将 pattern 向后移动一位重新比较。KMP 算法通过预处理 pattern，生成一个“部分匹配表”（通常称为 next 数组），利用已匹配的前缀信息，将 pattern 一次移动多位，避免 text 指针回退。部分匹配表（next 数组）定义：对于 pattern 的前缀子串 pattern[ 0:i]，其“最长相等前后缀”的长度（不包括自身）即为 next[ i ] 的值。前缀：指不包括最后一个字符的所有连续子串。后缀：指不包括第一个字符的所有连续子串。 "最长相等前后缀"：即前缀和后缀中相同的部分的最大长度。示例：pattern = "ABABCABAB" 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: "ABABC"，前缀 {"A","AB","ABA","ABAB"}，后缀 {"C","BC","ABC","BABC"}，无相同，next[ 4 ] = 0。继续计算得 next = [ 0, 0, 1, 2, 0, 1, 2, 3, 4 ]。构建 next 数组的步骤初始化：next[ 0 ] = 0，i = 1（当前子串末尾），j = 0（已匹配的前缀长度）。遍历 i 从 1 到 m-1：若 pattern[ i] == pattern[ j]，则 j++，next[ i ] = j，i++。若不等且 j > 0，则 j = next[ j-1 ]（回退到前一个前缀的匹配位置）。若 j=0 且不匹配，则 next[ i ] = 0，i++。示例（pattern="ABABCABAB"）： i=1, j=0: 'B' != 'A'，j=0 → next[ 1 ]=0, i=2。 i=2, j=0: 'A' == 'A' → j=1, next[ 2 ]=1, i=3。 i=3, j=1: 'B' == 'B' → j=2, next[ 3 ]=2, i=4。 i=4, j=2: 'C' != 'A'，j>0 → j=next[ 1 ]=0。现在 j=0, 'C' != 'A' → next[ 4 ]=0, i=5。继续过程，得到 next = [ 0,0,1,2,0,1,2,3,4 ]。使用 next 数组进行匹配初始化：i=0（text 指针），j=0（pattern 指针）。遍历 i 从 0 到 n-1：若 text[ i] == pattern[ j ]，则 i++, j++。若 j == m，表示完全匹配，记录位置 i-m，然后 j = next[ j-1 ]（继续寻找下一个匹配）。若字符不匹配：若 j > 0，则 j = next[ j-1 ]（pattern 向右移动，i 不变）。若 j=0，则 i++（pattern 开头就不匹配，text 指针前进）。示例（text="ABABDABACDABABCABAB", pattern="ABABCABAB"）：初始 i=0,j=0：匹配到 i=4,j=4时，text[ 4]='D' != pattern[ 4 ]='C'。 j=4>0 → j=next[ 3]=2（pattern 移动，比较 text[ 4] 与 pattern[ 2 ]）。 text[ 4]='D' != pattern[ 2]='A'，j=2>0 → j=next[ 1 ]=0。 j=0，i++ → i=5，重新开始匹配... 直到在 i=10 处找到完整匹配。总结 KMP 算法通过预处理 pattern 得到 next 数组，在匹配失败时智能移动 pattern，确保 text 指针不回溯，实现高效匹配。关键点在于理解最长相等前后缀的概念及 next 数组的构建与使用。