数据结构——字符串匹配算法：朴素的匹配算法和KMP算法（超详细解释 新手也能会学！！！）_kmp朴素

目录

一、字符串匹配问题定义

二、朴素匹配算法（Brute Force）

​​1. 核心思想​​

​​2. 伪代码实现​​

​​3. 时间复杂度分析​​

​​4. 缺陷​​

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

​​1. 核心思想​​

​​2. 最长公共前后缀（LPS）​：详细构建放在文章末尾​

​​3. next 数组构建​​

​​4. 匹配流程​​

​​5. 时间复杂度​​

四、算法对比与应用场景

五、总结

Fin：LPS究极详解

一、LPS表的核心作用​​

二、LPS表的构建步骤（动态规划思想）​​

三、LPS表如何用于匹配？​​

四、完整代码实现（Python）​​

五、为什么LPS能避免回溯？关键总结​​

---

一、字符串匹配问题定义

        给定​​文本串​​ T[0..n−1]（长度 n）和​​模式串​​ P[0..m−1]（长度 m，m≤n），目标是找到所有满足 T[s..s+m−1]=P[0..m−1] 的起始位置 s，称为​​合法移位​​（valid shift）。

---

二、朴素匹配算法（Brute Force）

​​1. 核心思想​​

• 枚举文本串 T 中所有长度为 m 的子串起点 s（s 范围：0 至 n−m）。
• 逐字符比较子串 T[s..s+m−1] 与模式串 P[0..m−1]。
• 若某字符失配（），则 s 右移一位，重新比较。

​​2. 伪代码实现​​

def naive_match(T, P): n = len(T) m = len(P) for s in range(0, n - m + 1): # 枚举所有起点 j = 0 while j < m and T[s + j] == P[j]: # 逐字符比较 j += 1 if j == m: # 完全匹配 return s return -1 # 无匹配

​​3. 时间复杂度分析​​

• ​​最坏情况​​：每次需比较 m 次才失配，共 n−m+1 次尝试，复杂度 O(m(n−m))≈O(mn)。
  • 例：T=\"AAAAA\"，P=\"AAAB\" 。
• ​​最好情况​​：首次比较即失配，复杂度 O(n)。
• ​​空间复杂度​​：O(1)，无需额外存储。

​​4. 缺陷​​

• ​​低效回溯​​：失配时文本串指针回溯至 s+1，模式串指针归零，重复比较大量字符。

---

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

​​1. 核心思想​​

• ​​避免回溯​​：失配时利用已匹配信息，将模式串右移多位，文本串指针不回溯。
• ​​关键工具​​：构建 next 数组（部分匹配表），存储模式串前缀的​​最长公共前后缀长度​​。

​​2. 最长公共前后缀（LPS）​：详细构建放在文章末尾​

• ​​定义​​：对子串 P[0..q]，其 LPS 是满足 P[0..k]=P[q−k..q] 的最大 k（k<q)。
• ​​示例​​：P=\"ABABC\" 的 LPS 计算： 子串（P[0..q]） 前缀 后缀 LPS（k） \"A\" [] [] 0 \"AB\" [\"A\"] [\"B\"] 0 \"ABA\" [\"A\",\"AB\"] [\"BA\",\"A\"] 1（\"A\"） \"ABAB\" [\"A\",\"AB\",\"ABA\"] [\"BAB\",\"AB\",\"B\"] 2（\"AB\"） \"ABABC\" 所有前缀 所有后缀 0

​​3. next 数组构建​​

• next[q] 表示 P[0..q] 的 LPS 长度。
• ​​动态规划递推​​：
  • next[0] = 0（单字符无真前缀）。
  • 设指针 i=1, j=0：
    • 若 P[i]=P[j]，则 next[i] = j + 1，i,j 右移。
    • 若 P[i]=P[j] 且 j>0，则 j=next[j−1]（回溯至前一个 LPS）。
    • 若 j=0，则 next[i] = 0，i 右移。

​​代码实现（Java）​​：

int[] computeNext(String P) { int m = P.length(); int[] next = new int[m]; next[0] = 0; int j = 0; for (int i = 1; i  0) { j = next[j - 1]; // 回溯至前一个 LPS } else { next[i] = 0; i++; } } return next;}

​​4. 匹配流程​​

1. 初始化文本串指针 i=0，模式串指针 j=0。
2. 比较 T[i] 与 P[j]：
   • 若相等，i 和 j 右移。
   • 若不等：
     • j>0：j=next[j−1]（模式串右移）。
     • j=0：i 右移。
3. 当 j=m 时，返回 i−j（匹配成功）。

​​匹配示例​​：
T=\"ABABABABC\", P=\"ABABC\"，`next = [0, 0, 1, 2, 0] )

• 失配于 T[4]（\'A\' vs \'C\'），j=next[3]=2 → 模式串右移 2 位，继续匹配。

​​5. 时间复杂度​​

• ​​预处理​​：构建 next 数组需 O(m)。
• ​​匹配​​：文本串指针 i 单调不减，复杂度 O(n)。
• ​​总计​​：O(m+n)，远优于朴素算法。

---

四、算法对比与应用场景

​​特性​​ 朴素匹配算法 KMP算法 ​​时间复杂度​​ O(mn)（最坏） O(m+n) ​​空间复杂度​​ O(1) O(m)（存储next） ​​优势​​ 实现简单，无需预处理 无回溯，适合长文本 ​​劣势​​ 重复比较，效率低 实现复杂，需额外空间 ​​适用场景​​ 短模式串、低频率匹配 长模式串、高频匹配需求

​​实际应用建议​​：

• ​​朴素算法​​：嵌入式系统、短文本（如 std::string::find 的实现）。
• ​​KMP算法​​：编译器词法分析、DNA序列比对（避免大量重复字符导致的低效）。

---

五、总结

        朴素匹配算法是字符串匹配的基础，但效率受限；​​KMP算法通过 next 数组跳过无效匹配，以空间换时间​​。理解KMP的关键在于掌握LPS的定义与 next 数组的构建逻辑。实际应用中需根据问题规模选择合适算法。进一步学习可参考Boyer-Moore、Sunday等优化算法。

---

---

---

Fin：LPS究极详解

        理解KMP算法的难点确实常集中在​​LPS（Longest Proper Prefix which is also Suffix，最长相同真前后缀）表​​的构建逻辑上。别担心，这里看完肯定能看懂，我们一起彻底攻克这个核心难点。

---

一、LPS表的核心作用​​

        在KMP算法中，LPS表（也称为前缀表或next数组）的作用是：​​当字符失配时，告诉模式串应该回退到哪个位置继续匹配​​。

• ​​为什么需要它？​​ 暴力匹配在失配时只能将模式串右移1位，而KMP利用LPS表跳过已确认匹配的字符，避免重复比较，大幅降低复杂度。
• ​​核心定义​​：对模式串位置i，LPS[i]表示子串P[0..i]的​​最长相同真前后缀的长度​​（真前后缀指不包含整个子串本身：也就是这里前缀的时候要排除掉从前往后的最后一位也就是位置i，后缀的时候排除掉从后往前的第一位也就是位置0）。

💡 ​​例​​：模式串 P = \"ABABC\"

• i=3时（子串\"ABAB\"）：
  • 前缀：\"A\", \"AB\", \"ABA\"
  • 后缀：\"B\", \"AB\", \"BAB\"
  • 最长相同前后缀：\"AB\" → 长度=2 → LPS[3] = 2。

---

二、LPS表的构建步骤（动态规划思想）​​

通过双指针分别是：j（前缀尾）和i（后缀尾）逐步计算，用模式串 P=\"ABABC\" 举例：

​​步骤​​ i位置 当前子串 操作 j变化 LPS[i] 解释 初始化 - - LPS[0]=0, j=0, i=1 - - 初始化 步骤1 i=1 \"AB\"

前缀：A

后缀：B

j=0 LPS[1]=0 无相同前后缀 步骤2 i=2 \"ABA\"

前缀：A,AB

后缀：A,BA

j++ → j=1 LPS[2]=1 前后缀\"A\"相同 步骤3 i=3 \"ABAB\"

前缀：A,AB,ABA

后缀：B,AB,BAB

j++ → j=2 LPS[3]=2 前后缀\"AB\"相同 步骤4 i=4 \"ABABC\"

前缀：A,AB,ABA,ABAB

后缀：
C,BC,ABC,BABC

回溯：j=LPS[j-1]=LPS[1]=0 LPS[4]=0 无相同前后缀

​​关键回溯逻辑​​（步骤4）：
        当P[i] ≠ P[j]时，j回溯到LPS[j-1]（即前一个字符的最长相同前后缀位置），避免重复比较已匹配前缀。

回溯原因：子串\"ABABC\"中，j=2指向\'A\'，i=4指向\'C\'不匹配。但\"ABA\"的最长相同前后缀是\"A\"（LPS[2]=1），所以将j回退到位置1（对应字符\'B\'），继续与i=4比较。

---

三、LPS表如何用于匹配？​​

以下列文本串T=\"ABABABABC\" 和模式串P=\"ABABC\"为例（LPS = [0,0,1,2,0]）：

1. ​​第一次匹配​​：
   • T[0..3] = \"ABAB\" 匹配 P[0..3]=\"ABAB\"
   • 失配位置：T[4]=\'A\' vs P[4]=\'C\'
2. ​​利用LPS跳过重复比较​​：
   • 失配时，模式串指针j回退到LPS[j-1] = LPS[3] = 2
   • 模式串右移，新匹配位置：P[2]对齐T[4]（相当于跳过2个字符）
3. ​​继续匹配​​：
   • 从T[4]=\'A\' vs P[2]=\'A\'开始 → 后续字符全部匹配成功。

​​跳过原理​​：
        子串\"ABAB\"的LPS[3]=2表明其后2字符\"AB\"与前缀\"AB\"相同，因此失配后可直接将前缀\"AB\"对齐到已匹配的\"AB\"上，跳过中间无效位置。

---

四、完整代码实现（Python）​​

def build_lps(pattern): m = len(pattern) lps = [0] * m j = 0 # 指针：前缀尾 for i in range(1, m): # 指针：后缀尾 # 字符不匹配时，回溯j到前一个LPS位置 while j > 0 and pattern[i] != pattern[j]: j = lps[j - 1] # 字符匹配，j右移并更新LPS if pattern[i] == pattern[j]: j += 1 lps[i] = j return lpsdef kmp_search(text, pattern): n, m = len(text), len(pattern) lps = build_lps(pattern) j = 0 # 模式串指针 for i in range(n): # 文本串指针 # 不匹配时，j回溯到LPS位置 while j > 0 and text[i] != pattern[j]: j = lps[j - 1] # 匹配时，j右移 if text[i] == pattern[j]: j += 1 if j == m: # 完全匹配 print(f\"匹配位置: {i - m + 1}\") j = lps[j - 1] # 继续搜索其他匹配 return -1 # 无匹配# 测试text = \"ABABABABC\"pattern = \"ABABC\"kmp_search(text, pattern) # 输出：匹配位置: 4

---

五、为什么LPS能避免回溯？关键总结​​

1. ​​空间换时间​​：LPS表存储模式串的自匹配信息，预处理时间O(m)，匹配时间O(n)。
2. ​​跳过的本质​​：利用已匹配部分的最长相同前后缀，直接将前缀对齐到后缀位置，跳过中间无重叠字符。
3. ​​类比理解​​：
   • 暴力匹配：每次失配，模式串右移1位（如幻灯片逐帧播放）。
   • KMP算法：失配时按LPS表跳转（如快进到关键帧）。

​​检验理解​​：尝试手动计算 P=\"AABAAB\" 的LPS表：

• 答案：[0,1,0,1,2,3]（子串\"AABAA\"的最长前后缀是\"AA\"，长度=2）。

彻底掌握LPS表，KMP算法就再无难点！