前言
KMP 算法是由 Knuth、Morris、Pratt 三位学者共同提出的字符串匹配高效算法，核心解决了传统暴力匹配算法中'主串指针回溯'的问题，将时间复杂度优化到线性级别。
C++算法
KMP 算法原理与 C++ 实现详解
KMP 算法是一种高效的字符串匹配算法，通过预处理模式串生成 next 数组，避免主串指针回溯。核心在于最长公共前后缀概念，利用已匹配信息优化回退逻辑。时间复杂度 O(n+m)，空间复杂度 O(m)。适用于文本查找、编译器词法分析及生物序列匹配等场景。
KMP 算法是一种高效的字符串匹配算法，通过预处理模式串生成 next 数组，避免主串指针回溯。核心在于最长公共前后缀概念，利用已匹配信息优化回退逻辑。时间复杂度 O(n+m)，空间复杂度 O(m)。适用于文本查找、编译器词法分析及生物序列匹配等场景。
KMP 算法是由 Knuth、Morris、Pratt 三位学者共同提出的字符串匹配高效算法，核心解决了传统暴力匹配算法中'主串指针回溯'的问题，将时间复杂度优化到线性级别。
字符串匹配问题：给定主串 S 和模式串 P，判断模式串 P 是否是主串 S 的子串，若存在，返回其在主串中首次出现的起始索引；若不存在，返回 -1。
暴力匹配（BF 算法）的思路是：主串指针 i 和模式串指针 j 从起始位置开始逐一匹配，若 S[i] != P[j]，则 i 回溯到 i-j+1，j 重置为 0，重新匹配。
动态演示
KMP 算法通过预处理模式串 P，生成 next 数组，让主串指针 i 永不回溯，仅通过模式串指针 j 的回退实现匹配，将时间复杂度优化到 O(n+m)。
理解 KMP 的关键，先掌握最长公共前后缀这个核心概念，再理解 next 数组的作用。
对于模式串的子串 P[0…j]，真前缀是指不包含最后一个字符的所有前缀，真后缀是指不包含第一个字符的所有后缀；最长公共前后缀就是真前缀和真后缀中长度最大的相等子串。
实例：字符串 P = 'abcab'，前缀有'a','ab','abc','abca', 后缀有'b','ab','cab','bcab'。最长公共前后缀字符串就是'ab'，长度为 2。
对于字符串"aaaaa"，求最长公共前后缀长度的过程如下:
对于字符串"abacb"，求最长公共前后缀长度的过程如下：
next 数组是 KMP 的核心，next 数组的长度等于模式串长度 m，next[j] 表示模式串子串 P[0…j] 的最长公共前后缀的长度。
当模式串跟主串匹配失败时，不用回退主串指针 i，只需要回退模式串的指针 j。而模式串移动多少？靠的就是 next 数组。
直觉理解： 当模式串跟主串已经匹配到 i，却在 i+1 失败时；前面已经匹配的那一段里，有一部分前缀 = 后缀，这部分前缀就可以'复用'，不用再重新匹配了。
图解
遍历模式串 p 的每一个子串，再对每个子串遍历所有长度的前后缀，这就是暴力求解 next 数组的方法（时间复杂度：O(m²)（m 为模式串长度））
// 暴力法计算 next 数组
std::vector<int> getNextBruteforce(const std::string& p){
int m = p.size();
std::vector<int> next(m, 0);
for(int i = 1; i < m; i++){
for(int k = i; k >= 1; k--){
if(p.substr(0, k) == p.substr(i - k + 1, k)){
next[i] = k;
break;
}
}
}
return next;
}
初始化两个指针：i 为后缀指针（从 1 开始，遍历模式串），j 为前缀指针（从 0 开始，记录最长公共前后缀的长度），next[0] = 0（单个字符无真前后缀）。
遍历模式串 P[1…m-1]，分两种情况更新 i 和 j，并赋值 next[i]：
(1). 动态规划的思路 计算 next[i] 时，我们已经知道 next[0], next[1], …, next[i-1]。我们利用已计算的 next 值来高效计算 next[i]。
(2). 算法的直观解释
步骤 1：基础情况（i=1）—— 验证初始步骤正确 当 i=1 时，处理子串 P[0…1]：
结论：基础情况（i=1）的 next 值计算完全符合定义，正确。
步骤 2：归纳假设 假设对于所有 0 ≤ k < i，next[k] 的计算都是正确的 —— 即 next[k] 是 P[0…k] 的最长相等真前后缀长度。
步骤 3：归纳推导（Inductive Step）—— 证明 next[i] 正确 基于归纳假设，分析 P[0…i] 的最长相等真前后缀长度（即 next[i]），分两种核心情况：
情况 A：如果 P[i] == P[j]（j=next[i-1]）
实例验证：模式串 AAAB，i=2（P[2]=A），j=next[1]=1（P[0…1] 的最长长度 1）：
情况 B：如果 P[i] != P[j]（j=next[i-1]） 此时 P[0…i-1] 的最长前后缀加 P[i] 后不匹配，需要找 P[0…i-1] 的次长相等真前后缀，直到找到匹配或 j=0：
实例验证：模式串 AAAB，i=3（P[3]=B），j=next[2]=2（P[0…2] 的最长长度 2）：
迭代法中 j = next[j-1] 的回退逻辑，是正确性的关键补充 —— 它保证了'每次回退都找当前最优的次长长度'，而非从头枚举（如暴力法），既高效又正确：
最终 next 数组：[0,1,2,0]。
在以模式串 P='abcabd'（m=6）为例，一步步计算 next 数组，让你彻底掌握：
// 生成模式串的 next 数组
std::vector<int> getNext(const std::string& p){
int m = p.size();
std::vector<int> next(m, 0); // next 数组初始化为 0，next[0] 固定为 0
int j = 0; // 前缀指针，记录最长相等前后缀的长度
for(int i = 1; i < m;++i){ // 后缀指针 i 从 1 开始遍历
// 情况 2：P[i] != P[j]，回退 j，直到 j=0 或匹配成功
while(j > 0 && p[i] != p[j]){
j = next[j - 1];
}
// 情况 1：P[i] == P[j]，j++，更新 next[i]
if(p[i] == p[j]){
j++;
}
next[i] = j;
}
return next;
}
主串 S 指针 i、模式串 P 指针 j 初始均为 0，遍历主串进行匹配：
实例 1：主串 S = 'AAAAAAB'，模式串 P = 'AAAB'
匹配前准备
逐步骤匹配过程
动图演示
实例 2：主串 S = 'abcabcabdabc'，模式串 P = 'abcabd'
匹配前准备
逐步骤匹配过程
动图演示
// KMP 匹配主函数：返回模式串 p 在主串 s 中首次出现的起始索引，失败返回 -1
int kmpSearch(const std::string& s, const std::string& p){
int n = s.size();
int m = p.size();
if(m == 0) return 0; // 模式串为空，默认匹配成功
std::vector<int> next = getNext(p);
int j = 0; // 模式串指针
for(int i = 0; i < n;++i){ // 主串指针 i 不回溯，一直前进
// 匹配失败，根据 next 数组回退 j
while(j > 0 && s[i] != p[j]){
j = next[j - 1];
}
// 匹配成功，模式串指针前进
if(s[i] == p[j]){
j++;
}
// 模式串全部匹配成功，返回起始索引
if(j == m){ return i - m + 1; }
}
return -1; // 匹配失败
}
KMP 算法的时间复杂度分为 next 数组生成的时间复杂度和核心匹配的时间复杂度，空间复杂度为 next 数组的存储空间。
KMP 算法需要额外存储 next 数组，数组长度为模式串长度 m，因此空间复杂度为 O(m)。
KMP 算法作为经典的线性字符串匹配算法，在工程中应用广泛，典型场景包括：
KMP 算法的核心是'利用已匹配信息，避免重复比较'，而 next 数组是实现这一思想的关键，记住以下 3 个核心点，就能彻底掌握 KMP：
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online