前言：
本文涵盖KMPKMPKMP算法的详细步骤，大家有什么建议可以在评论区说哦！
加精啦！！！感谢AC君赞助！！！
竟然榜7了！
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
广告：
求加团！
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
> 目录（CONTENTS）：
>
>
> > 第一部分：导言
> >
> >
> > 第二部分：什么是 KMP 算法
> >
> >
> > 第三部分：KMP 算法的核心概念与预处理
> >
> >
> > 第四部分：KMP 算法的匹配过程与实现
> >
> >
> > 第五部分：刷题时光
> >
> >
> > 第六部分：常见踩坑点与避坑指南
> >
> >
> > 第七部分：常见问题与注意事项
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第一部分：导言:
在字符串处理场景中，我们经常需要解决 “模式匹配” 问题 —— 比如从一篇文章里找某个关键词、在日志中匹配特定指令，这时候最直接的思路是 “暴力匹配”：用模式串的每个字符依次对比主串的对应位置，不匹配就回溯主串重新开始。
但暴力匹配效率极低，比如主串是"AAAAA...A"（1000 个 A），模式串是"AAAB"，每次匹配到最后一个字符才失败，主串频繁回溯导致时间复杂度达到O(N*M)（N 为主串长度，M 为模式串长度）。
为此，我们需要更高效的算法 ——KMP 算法。它通过预处理模式串生成 “部分匹配表”（PMT），避免主串回溯，将时间复杂度优化到O(N+M)，是字符串匹配的经典高效方案。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第二部分：什么是 KMP 算法：
KMP 算法由 KNUTH、MORRIS 和 PRATT 三位科学家共同提出，核心思想是利用模式串自身的前缀后缀匹配信息，在匹配失败时让模式串 “少后退”，从而跳过不必要的对比步骤。
核心问题：为什么暴力匹配效率低？
假设主串为S = "ABCABDABCAB"，模式串为P = "ABCAB"：
> ·暴力匹配时，前 4 个字符 "ABCA" 均匹配，第 5 个字符 S [4] = 'X'（此处替换为与 'B' 不匹配的字符，如 'X'）与 P [4] = 'B' 不匹配，此时主串会回溯到 S [1]，模式串回到 P [0] 重新开始。
> ·但观察模式串"ABCAB"，其前 4 个字符"ABCA"的前缀"A"和后缀"A"是最长匹配的（长度 1）。这意味着主串中S[3] = 'A'（对应模式串P[3] = 'A'）其实可以直接与模式串的P[1]继续匹配，无需回溯主串。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第三部分：KMP 算法的核心概念与预处理：
在学习 KMP 的实现前，必须掌握两个核心概念：前缀后缀和部分匹配表（PMT）。
3.1. 前缀与后缀：
> ·前缀：字符串中除最后一个字符外，所有以第一个字符开头的连续子串。例："ABCAB"的前缀为["A", "AB", "ABC", "ABCA"]。
> ·后缀：字符串中除第一个字符外，所有以最后一个字符结尾的连续子串。例："ABCAB"的后缀为["B", "AB", "CAB", "BCAB"]。
> ·最长公共前缀后缀（LCP）：前缀和后缀中长度最长的相同子串。例："ABCAB"的 LCP 为"AB"，长度为 2。
3.2. 部分匹配表（PMT）：
部分匹配表（也称NEXT数组）是 KMP 的核心，它存储了模式串中每个位置的前缀子串的 LCP 长度。
> ·下标：模式串的字符位置（从 0 开始）。
> ·值：该位置前的前缀子串（即P[0..I-1]）的 LCP 长度。
如何构建 PMT（以模式串P = "ABCAB"为例）：
模式串字符 p[0] = 'A' p[1] = 'B' p[2] = 'C' p[3] = 'A' p[4] = 'B' 前缀子串 空串 "A" "AB" "ABC" "ABCA" LCP 长度 0 0 0 1 2 PMT 值 0 0 0 1 2
构建 PMT 的代码实现：
核心逻辑：用双指针I（指向后缀末尾）和J（指向前缀末尾）遍历模式串，通过对比字符更新 LCP 长度：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第四部分：KMP 算法的匹配过程与实现：
有了 PMT，KMP 的匹配过程就非常清晰了：用两个指针分别遍历主串S和模式串P，匹配失败时通过 PMT 调整模式串指针，主串指针始终不回溯。
匹配步骤
1.初始化主串指针I = 0，模式串指针J = 0，并构建模式串的 PMT。
2.遍历主串：
> ·若S[I] == P[J]：两个指针同时后移（I++，J++）。
>
> ·若S[I] != P[J]：
>
> > ·若J > 0：通过 PMT 将J调整为PMT[J-1]（利用前缀后缀匹配信息跳过无效对比）。
> >
> > ·若J == 0：主串指针后移（I++），模式串从开头重新匹配。
3.当J == P.SIZE()时，说明模式串完全匹配，返回匹配的起始位置（I - J）；遍历结束未匹配则返回 - 1。
完整代码实现：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第五部分：刷题时光：
例题 1：LEETCODE 28. 找出字符串中第一个匹配项的下标
题目大意：给你两个字符串HAYSTACK（主串）和NEEDLE（模式串），请返回NEEDLE在HAYSTACK中首次出现的下标。如果NEEDLE不是HAYSTACK的一部分，则返回-1。
解题思路：直接套用 KMP 算法模板，核心是构建 PMT 并执行匹配逻辑。
完整代码：
例题 2：查找模式串在主串中的所有匹配位置
题目大意：读入主串S和模式串P，输出P在S中所有出现的起始下标，若未匹配则输出 “无匹配”。
解题思路：在 KMP 匹配中，当J == M（匹配成功）时，不直接返回，而是通过 PMT 调整J（J = PMT[J-1]），继续查找后续匹配。
核心代码片段：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第六部分：常见踩坑点与避坑指南：
KMP 算法的逻辑看似清晰，但在编码和理解过程中极易陷入细节陷阱，以下是高频踩坑点及解决方法：
1. PMT 构建：用 “IF” 代替 “WHILE” 回溯 J，导致 LCP 计算错误：
坑点描述：
构建 PMT 时，当P[I] != P[J]，新手常误用IF语句单次回溯J（如IF (J>0) J=PMT[J-1]），而非WHILE循环，导致无法找到最长的有效前缀后缀。
反例代码（错误）
问题分析：
以模式串P = "ABABAC"为例：
> ·当I=4（P[I]='A'）、J=3（P[J]='B'）时，P[I] != P[J]，需回溯J到PMT[2] = 2（P[2]='A'）。此时P[4]='A' == P[2]='A'，J应更新为 3。
> ·若用IF，仅回溯一次就停止；若P[J]仍不匹配（如更复杂的模式串），会导致 LCP 长度计算偏短，后续匹配出错。
避坑方案：
必须用WHILE循环回溯J，直到J=0或P[I] == P[J]，确保找到最长的公共前缀后缀：
2. 匹配时：主串指针回溯，违背 KMP 核心逻辑：
坑点描述：
受暴力匹配思维影响，在S[I] != P[J]时，不自觉地让主串指针I回溯（如I = I - J + 1），导致时间复杂度退化为O(N*M)，失去 KMP 的效率优势。
反例代码（错误）
问题分析：
KMP 的核心优化是 “主串不回溯”，所有调整仅针对模式串指针J。主串指针I一旦后移，就不再退回，这是保证O(N+M)复杂度的关键。
避坑方案：
牢记：匹配过程中主串指针I只做自增，绝不回溯。所有匹配失败的调整都通过修改J实现。
3. 边界处理：忽略模式串为空或长度大于主串的情况
坑点描述：
编码时未考虑极端边界场景，如模式串P为空、P.SIZE() > S.SIZE()，导致数组越界或返回错误结果。
反例代码（错误）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第七部分：常见问题与注意事项：
1.PMT 与 NEXT 数组的区别：有些资料中NEXT数组是 PMT 的 “右移 + 1” 版本（如NEXT[0] = -1），本质逻辑一致，只是实现时指针调整方式略有不同，本文采用原始 PMT 定义更易理解。
2.模式串为空的处理：根据题目要求，通常模式串为空时返回 0（匹配开头）或空列表。
3.字符类型适配：KMP 算法适用于所有可比较的字符类型（如大写字母、小写字母、数字），无需修改核心逻辑。
4.PMT 构建的易错点：当P[I] != P[J]时，必须用WHILE循环回溯J（而非IF），确保找到最长的有效前缀后缀。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
尾声：
> 特别鸣谢：
>
> > 排版： @AC是最好的
> >
> > 标题：@༺དༀ༒∞░∞༒ༀཌ༻
> >
> > 前言：@༺ཌༀཉི༒白·羊༒༃ༀད༻
> >
> > 指正错误&建议：@༺ཌༀཉི༒白·羊༒༃ༀད༻
创作不易，给一个赞吧，求求了
