KMP 算法（Knuth-Morris-Pratt 算法）
字数 2392 2025-10-27 21:57:01

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

题目描述
给定一个文本串 text 和一个模式串 pattern，要求在文本串中查找模式串首次出现的起始位置（如果存在）。例如，text = "ABABDABACD"，pattern = "ABA"，应返回位置 0（索引从 0 开始）。若模式串不存在于文本串中，则返回 -1。
核心难点：避免在匹配失败时从头重新比较，而是利用已匹配的信息跳过不必要的检查。

解题过程循序渐进讲解

步骤 1：理解暴力匹配的缺陷
暴力匹配的做法是：

  1. 从文本串的每个字符开始，与模式串逐字符比较。
  2. 若遇到不匹配的字符，则文本串指针回退到本次匹配起始位置的下一个字符，模式串指针回退到开头，重新开始匹配。
    缺陷：例如 text = "AAAAB"，pattern = "AAB"。当匹配到 text[2] 和 pattern[2] 失败时，暴力法会让文本串指针从位置 1 重新开始，但事实上模式串的前缀 "AA" 的信息可以被利用来避免回退。

步骤 2：引入“最长公共前后缀”概念

  • 前缀：不包含最后一个字符的连续子串（如 "ABC" 的前缀有 "A", "AB"）。
  • 后缀：不包含第一个字符的连续子串（如 "ABC" 的后缀有 "BC", "C"）。
  • 最长公共前后缀（LPS）：对于一个子串，其最长的相等前缀和后缀的长度。
    • 例："ABAB"：前缀有 "A", "AB", "ABA"；后缀有 "B", "AB", "BAB"。公共前后缀有 "AB"，长度 = 2。
    • 例："AAA"：最长公共前后缀是 "AA"，长度 = 2。

步骤 3：构建 Next 数组（部分匹配表）
Next 数组（或称 π 数组、LPS 数组）定义为：

  • next[i] 表示模式串 pattern[0..i] 这个子串的 最长公共前后缀的长度。
  • 注意：这个公共前后缀不能是子串本身（即长度必须小于 i+1）。

手动计算示例（模式串 "ABABC"）：

  • i=0，子串 "A"：无公共前后缀，next[0] = 0。
  • i=1，子串 "AB"：前缀 "A"，后缀 "B"，无公共，next[1] = 0。
  • i=2，子串 "ABA"：前缀 "A" 与后缀 "A" 相等，长度 1；前缀 "AB" 与后缀 "BA" 不相等。所以 next[2] = 1。
  • i=3，子串 "ABAB"：前缀 "A" 与后缀 "B" 不匹配；前缀 "AB" 与后缀 "AB" 相等，长度 2。next[3] = 2。
  • i=4，子串 "ABABC"：最长公共前后缀长度为 0，next[4] = 0。
    最终 Next 数组：[0, 0, 1, 2, 0]。

步骤 4：Next 数组的代码构建方法
使用双指针 i 和 j：

  • i 指向当前子串的末尾（从 1 开始，因为 next[0] 一定为 0）。
  • j 指向上一个子串的最长公共前后缀的长度（即 next[i-1]）。
    算法：
  1. 初始化 next[0] = 0，j = 0，i = 1。
  2. 当 i < n 时循环：
    • 若 pattern[i] == pattern[j]，则 j++，next[i] = j，i++。
    • 否则：
      • 如果 j > 0，令 j = next[j-1]（回退到前一个最长公共前后缀的长度）。
      • 如果 j == 0，则 next[i] = 0，i++。

示例（"ABABC"）：

  • 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；再比 'C' != 'A'，j=0 → next[4]=0。
    结果与手动计算一致。

步骤 5：利用 Next 进行匹配

  1. 初始化文本串指针 i = 0，模式串指针 j = 0。
  2. 循环直到文本串或模式串遍历完：
    • 若 text[i] == pattern[j]，则 i++, j++。
    • 否则：
      • 若 j > 0，令 j = next[j-1]（利用公共前后缀跳过已匹配前缀）。
      • 若 j == 0，则 i++（模式串从头开始匹配文本串的下一个字符）。
  3. 若 j == n（模式串匹配完成），返回 i - n；否则返回 -1。

示例（text = "ABABABC", pattern = "ABABC"）：

  • i=0, j=0：匹配 "A" → i=1, j=1。
  • i=1, j=1：匹配 "B" → i=2, j=2。
  • i=2, j=2：匹配 "A" → i=3, j=3。
  • i=3, j=3：匹配 "B" → i=4, j=4。
  • i=4, j=4：'A' != 'C'，j>0 → j=next[3]=2。
  • 比较 text[4]='A' 与 pattern[2]='A' → 匹配，i=5, j=3。
  • 继续匹配直到 j=5（完成），返回 i - n = 5 - 5 = 0（实际起始位置是 0）。

总结
KMP 算法通过预处理模式串得到 Next 数组，在匹配失败时通过 Next 数组避免文本串指针回退，将时间复杂度从暴力法的 O(m*n) 优化到 O(m+n)。关键理解 Next 数组的含义及其在匹配过程中的“跳跃”逻辑。

KMP 算法（Knuth-Morris-Pratt 算法） 题目描述 给定一个文本串 text 和一个模式串 pattern ，要求在文本串中查找模式串首次出现的起始位置（如果存在）。例如， text = "ABABDABACD" ， pattern = "ABA" ，应返回位置 0（索引从 0 开始）。若模式串不存在于文本串中，则返回 -1。 核心难点 ：避免在匹配失败时从头重新比较，而是利用已匹配的信息跳过不必要的检查。 解题过程循序渐进讲解 步骤 1：理解暴力匹配的缺陷 暴力匹配的做法是： 从文本串的每个字符开始，与模式串逐字符比较。 若遇到不匹配的字符，则文本串指针回退到本次匹配起始位置的下一个字符，模式串指针回退到开头，重新开始匹配。 缺陷 ：例如 text = "AAAAB" ， pattern = "AAB" 。当匹配到 text[2] 和 pattern[2] 失败时，暴力法会让文本串指针从位置 1 重新开始，但事实上模式串的前缀 "AA" 的信息可以被利用来避免回退。 步骤 2：引入“最长公共前后缀”概念 前缀 ：不包含最后一个字符的连续子串（如 "ABC" 的前缀有 "A", "AB"）。 后缀 ：不包含第一个字符的连续子串（如 "ABC" 的后缀有 "BC", "C"）。 最长公共前后缀 （LPS）：对于一个子串，其最长的相等前缀和后缀的长度。 例： "ABAB" ：前缀有 "A", "AB", "ABA"；后缀有 "B", "AB", "BAB"。公共前后缀有 "AB"，长度 = 2。 例： "AAA" ：最长公共前后缀是 "AA"，长度 = 2。 步骤 3：构建 Next 数组（部分匹配表） Next 数组（或称 π 数组、LPS 数组）定义为： next[i] 表示模式串 pattern[0..i] 这个子串的 最长公共前后缀的长度 。 注意：这个公共前后缀不能是子串本身（即长度必须小于 i+1）。 手动计算示例 （模式串 "ABABC" ）： i=0 ，子串 "A" ：无公共前后缀， next[0] = 0 。 i=1 ，子串 "AB" ：前缀 "A"，后缀 "B"，无公共， next[1] = 0 。 i=2 ，子串 "ABA" ：前缀 "A" 与后缀 "A" 相等，长度 1；前缀 "AB" 与后缀 "BA" 不相等。所以 next[2] = 1 。 i=3 ，子串 "ABAB" ：前缀 "A" 与后缀 "B" 不匹配；前缀 "AB" 与后缀 "AB" 相等，长度 2。 next[3] = 2 。 i=4 ，子串 "ABABC" ：最长公共前后缀长度为 0， next[4] = 0 。 最终 Next 数组： [0, 0, 1, 2, 0] 。 步骤 4：Next 数组的代码构建方法 使用双指针 i 和 j ： i 指向当前子串的末尾（从 1 开始，因为 next[0] 一定为 0）。 j 指向上一个子串的最长公共前后缀的长度（即 next[i-1] ）。 算法： 初始化 next[0] = 0 ， j = 0 ， i = 1 。 当 i < n 时循环： 若 pattern[i] == pattern[j] ，则 j++ ， next[i] = j ， i++ 。 否则： 如果 j > 0 ，令 j = next[j-1] （回退到前一个最长公共前后缀的长度）。 如果 j == 0 ，则 next[i] = 0 ， i++ 。 示例 （ "ABABC" ）： 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；再比 'C' != 'A' ，j=0 → next[4]=0 。 结果与手动计算一致。 步骤 5：利用 Next 进行匹配 初始化文本串指针 i = 0 ，模式串指针 j = 0 。 循环直到文本串或模式串遍历完： 若 text[i] == pattern[j] ，则 i++ , j++ 。 否则： 若 j > 0 ，令 j = next[j-1] （利用公共前后缀跳过已匹配前缀）。 若 j == 0 ，则 i++ （模式串从头开始匹配文本串的下一个字符）。 若 j == n （模式串匹配完成），返回 i - n ；否则返回 -1。 示例 （ text = "ABABABC" , pattern = "ABABC" ）： i=0, j=0：匹配 "A" → i=1, j=1。 i=1, j=1：匹配 "B" → i=2, j=2。 i=2, j=2：匹配 "A" → i=3, j=3。 i=3, j=3：匹配 "B" → i=4, j=4。 i=4, j=4： 'A' != 'C' ，j>0 → j=next[ 3 ]=2。 比较 text[4]='A' 与 pattern[2]='A' → 匹配，i=5, j=3。 继续匹配直到 j=5（完成），返回 i - n = 5 - 5 = 0（实际起始位置是 0）。 总结 KMP 算法通过预处理模式串得到 Next 数组，在匹配失败时通过 Next 数组避免文本串指针回退，将时间复杂度从暴力法的 O(m* n) 优化到 O(m+n)。关键理解 Next 数组的含义及其在匹配过程中的“跳跃”逻辑。