前言
KMP 算法是由 Knuth、Morris、Pratt 三位学者共同提出的字符串匹配高效算法，核心解决了传统暴力匹配算法中'主串指针回溯'的问题，将时间复杂度优化到线性级别。
一、算法概述
1. 解决的问题
字符串匹配问题：给定主串 S 和模式串 P，判断模式串 P 是否是主串 S 的子串，若存在，返回其在主串中首次出现的起始索引；若不存在，返回 -1。
2. 传统暴力匹配的问题
暴力匹配（BF 算法）的思路是：主串指针 i 和模式串指针 j 从起始位置开始逐一匹配，若 S[i] != P[j]，则 i 回溯到 i-j+1，j 重置为 0，重新匹配。
- 问题核心：主串指针的回溯导致大量重复比较，最坏时间复杂度为 O(n*m)（n 为主串长度，m 为模式串长度）。
- 例子：主串 S = 'AAAAAAB'，模式串 P = 'AAAB'，暴力匹配会在第 4 位匹配失败后反复回溯，效率极低。
动态演示
3. KMP 算法的核心改进
KMP 算法通过预处理模式串 P，生成 next 数组，让主串指针 i 永不回溯，仅通过模式串指针 j 的回退实现匹配，将时间复杂度优化到 O(n+m)。
- 核心思想：当 S[i] != P[j] 时，利用已匹配的前缀信息，让 j 回退到当前位置的最长公共前后缀的后缀末尾下一位，而非直接重置为 0，避免重复比较。
二、算法核心原理
理解 KMP 的关键，先掌握最长公共前后缀这个核心概念，再理解 next 数组的作用。
关键概念：最长公共前后缀（真前后缀）
对于模式串的子串 P[0…j]，真前缀是指不包含最后一个字符的所有前缀，真后缀是指不包含第一个字符的所有后缀；最长公共前后缀就是真前缀和真后缀中长度最大的相等子串。
- 注意：真前后缀不能是子串本身，否则无意义
- 若子串无相等的真前后缀，最长公共前后缀长度为 0（如 P[0…1]=AB）。
实例：字符串 P = 'abcab'，前缀有'a','ab','abc','abca', 后缀有'b','ab','cab','bcab'。最长公共前后缀字符串就是'ab'，长度为 2。
对于字符串"aaaaa"，求最长公共前后缀长度的过程如下:
对于字符串"abacb"，求最长公共前后缀长度的过程如下：
三、next 数组计算详解（KMP 的灵魂）
next 数组是 KMP 的核心，next 数组的长度等于模式串长度 m，next[j] 表示模式串子串 P[0…j] 的最长公共前后缀的长度。
1. 为什么需要 next？
当模式串跟主串匹配失败时，不用回退主串指针 i，只需要回退模式串的指针 j。而模式串移动多少？靠的就是 next 数组。
直觉理解： 当模式串跟主串已经匹配到 i，却在 i+1 失败时；前面已经匹配的那一段里，有一部分前缀 = 后缀，这部分前缀就可以'复用'，不用再重新匹配了。
- 作用：当 S[i] != P[j+1] 时，模式串 j 需要回退到 next[j] 的位置，继续匹配；
- 本质：next 数组是模式串的自我匹配，通过预处理模式串，记录每个位置的最长公共前后缀长度，避免匹配失败时的重复比较。
图解
2. next 的暴力方法求解
遍历模式串 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;
}
3. next 数组的计算思路（迭代法）
初始化两个指针：i 为后缀指针（从 1 开始，遍历模式串），j 为前缀指针（从 0 开始，记录最长公共前后缀的长度），next[0] = 0（单个字符无真前后缀）。
遍历模式串 P[1…m-1]，分两种情况更新 i 和 j，并赋值 next[i]：
- 情况 1: P[i] == P[j] 说明当前字符匹配，最长公共前后缀长度 + 1，执行：j++，next[i] = j，i++。
- 情况 2: P[i] != P[j]
说明当前字符不匹配，需要回退前缀指针 j，利用已计算的 next 数组信息，执行：j = next[j-1]（直到 j == 0 或 P[i] == P[j]）。
- 若回退后 j == 0 且 P[i] != P[j]：next[i] = 0，i++；
- 若回退后 P[i] == P[j]：执行情况 1 的逻辑。
4. 迭代法的正确性分析
(1). 动态规划的思路 计算 next[i] 时，我们已经知道 next[0], next[1], …, next[i-1]。我们利用已计算的 next 值来高效计算 next[i]。
(2). 算法的直观解释
步骤 1：基础情况（i=1）—— 验证初始步骤正确 当 i=1 时，处理子串 P[0…1]：
- 初始化 j=next[0]=0（P[0] 的最长真前后缀长度为 0，符合定义）；
- 若 P[1] == P[0]（如模式串 AA）
- 执行情况 1：j++=1，next[1]=1——P[0…1] 的最长相等真前后缀长度为 1（P[0]=P[1]），符合定义；
- 若 P[1] != P[0]（如模式串 AB）：
- 执行情况 2：j=0 且 P[1] != P[0]，next[1]=0 —— 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]）
- 由归纳假设，j = next[i-1] 是 P[0…i-1] 的最长相等真前后缀长度 → 前缀 P[0…j-1] = 后缀 P[i-j…i-1]；
- 现在 P[i] == P[j]，相当于给这两个相等的前后缀'末尾各加一个相同字符' → 前缀 P[0…j] = 后缀 P[i-j…i]；
- 这个新的长度 j+1 是 P[0…i] 的最长相等真前后缀长度（因为 j 已经是 P[0…i-1] 的最长长度，加 1 后自然是当前最长）；
- 迭代法执行 j++、next[i]=j，完全匹配这个最长长度，因此 next[i] 正确。
实例验证：模式串 AAAB，i=2（P[2]=A），j=next[1]=1（P[0…1] 的最长长度 1）：
- P[2]=A == P[1]=A → j++=2，next[2]=2；
- P[0…2]（AAA）的最长相等真前后缀长度为 2（AA ↔ AA），符合定义。
情况 B：如果 P[i] != P[j]（j=next[i-1]） 此时 P[0…i-1] 的最长前后缀加 P[i] 后不匹配，需要找 P[0…i-1] 的次长相等真前后缀，直到找到匹配或 j=0：
- 为什么回退 j = next[j-1]？ 由归纳假设，next[j-1] 是 P[0…j-1] 的最长相等真前后缀长度 → 这意味着： ① P[0…next[j-1]-1] = P[j-next[j-1]…j-1]（P[0…j-1] 的最长相等前后缀）； ② 结合 P[0…j-1] = P[i-j…i-1]（j=next[i-1] 的定义），可推导出 P[0…next[j-1]-1] = P[i-next[j-1]…i-1]； ③ 因此 next[j-1] 是 P[0…i-1] 的次长相等真前后缀长度（最优回退，无需从头找）。
- 回退后的两种子情况： ① 回退后 P[i] == P[j]：执行场景 1 的逻辑，next[i] = j+1（次长 + 1 成为 P[0…i] 的最长长度）； ② 回退后 j=0 且 P[i] != P[j]：P[0…i] 无相等真前后缀，next[i]=0，符合定义。
实例验证：模式串 AAAB，i=3（P[3]=B），j=next[2]=2（P[0…2] 的最长长度 2）：
- P[3] = B != P[2] = A → 回退 j=next[1] = 1；
- P[3] = B != P[1] = A → 回退 j=next[0] = 0；
- j = 0 且 P[3] != P[0] → next[3] = 0；
- P[0…3]（AAAB）无相等真前后缀，符合定义。
5. 回退逻辑的'最优性'（为什么不从头找？）
迭代法中 j = next[j-1] 的回退逻辑，是正确性的关键补充 —— 它保证了'每次回退都找当前最优的次长长度'，而非从头枚举（如暴力法），既高效又正确：
- 无重复验证：利用已计算的 next 值（归纳假设已证明正确），直接跳转到次长长度，避免重复验证；
- 最优性：next[j-1] 是 P[0…j-1] 的最长长度，因此推导得到的是 P[0…i-1] 的次长长度（若存在更长的，早就在之前的迭代中被找到）；
- 终止条件：回退到 j=0 时，已穷尽所有可能的次长长度，此时直接判断 P[i] 与 P[0] 是否匹配即可。
6. 实例计算 next 数组（手把手教）
- 以模式串 P='AAAB'（m=4）为例，一步步计算 next 数组，让你彻底掌握：
- 初始化：next[0] = 0，i=1，j=0。
- i=1，P[1]=A，P[j]=P[0]=A：相等，j=1，next[1]=1，i=2；
- i=2，P[2]=A，P[j]=P[1]=A：相等，j=2，next[2]=2，i=3；
- i=3，P[3]=B，P[j]=P[2]=A：不相等，j=next[1]=1； 回退后 P[3]=B != P[1]=A，j=next[0]=0; 回退后 P[3]=B != P[0]=A，next[3]=0，i=4（遍历结束）。
-
最终 next 数组：[0,1,2,0]。
-
在以模式串 P='abcabd'（m=6）为例，一步步计算 next 数组，让你彻底掌握：
- 初始化：next[0] = 0，i=1，j=0。
- i=1，P[1]=b，P[j]=P[0]=a：不相等，j=0，next[1]=0，i=2；
- i=2，P[2]=c，P[j]=a：不相等，j=0，next[2]=0，i=3；
- i=3，P[3]=a，P[j]=a：相等，j=1，next[3]=1，i=4；
- i=4，P[4]=b，P[j]=P[1]=b：相等，j=2，next[4]=2，i=5；
- i=5，P[5]=d，P[j]=P[2]=c：不相等，j=next[1]=0； 回退后 P[5]=d != P[0]=a，next[5]=0，i=6（遍历结束）；
- 最终 next 数组：[0,0,0,1,2,0]。
7. C++ 代码实现
// 生成模式串的 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;
}
四、KMP 算法
1. KMP 的匹配逻辑（核心）
主串 S 指针 i、模式串 P 指针 j 初始均为 0，遍历主串进行匹配：
- 若 S[i] == P[j]：i++，j++，继续匹配；
- 若 S[i] != P[j]：
- 若 j > 0：j = next[j-1]（利用 next 数组回退 j，不回溯 i）；
- 若 j == 0：i++（模式串第一个字符就不匹配，主串指针后移）；
- 终止条件：
- 若 j == m（m 为模式串长度）：匹配成功，返回起始索引 i-j；
- 若 i == n（n 为主串长度）且 j < m：匹配失败，返回 -1。
2. KMP 匹配过程
实例 1：主串 S = 'AAAAAAB'，模式串 P = 'AAAB'
匹配前准备
- 主串 S='AAAAAAB'（长度 n=7）
- 模式串 P='AAAB'（长度 m=4）
- 已计算好的 next 数组：next = [0,1,2,0]；
- 初始化：i=0（主串指针，永不回溯），j=0（模式串指针，匹配失败时通过 next 数组回退）。
逐步骤匹配过程
- i=0，j=0：S[0]=A，P[0]=A：相等，i=1，j=1；
- i=1，j=1：S[1]=A，P[1]=A：相等，i=2，j=2；
- i=2，j=2：S[2]=A，P[2]=A：相等，i=3，j=3；
- i=3，j=3：S[3]=A，P[3]=B：不相等，触发 j 回退；j = next[j-1] = next[2] = 2（核心：利用 next 数组回退，而非重置为 0）；
- i=3，j=2：S[3]=A，P[2]=A：相等，i=4，j=3；
- i=4，j=3：S[4]=A，P[3]=B：不相等，触发 j 回退；j = next[j-1] = next[2] = 2；
- i=4，j=2：S[4]=A，P[2]=A：相等，i=5，j=3；
- i=5，j=3：S[5]=A，P[3]=B：不相等，触发 j 回退；j = next[j-1] = next[2] = 2；
- i=5，j=2：S[5]=A，P[2]=A：相等，i=6，j=3；
- i=6，j=3：S[6]=B，P[3]=B：相等，i=7，j=4；此时 j=m=4（模式串全部匹配完成），匹配成功；起始索引 = i - m = 7 - 4 = 3；
动图演示
实例 2：主串 S = 'abcabcabdabc'，模式串 P = 'abcabd'
匹配前准备
- 主串 S='abcabcabdabc'（长度 n=11）
- 模式串 P='abcabd'（长度 m=6）
- 已计算好的 next 数组：next = [0,0,0,1,2,0]；
- 初始化：i=0（主串指针，永不回溯），j=0（模式串指针，匹配失败时通过 next 数组回退）。
逐步骤匹配过程
- i=0，j=0：S[0]=a，P[0]=a：相等，i=1，j=1；
- i=1，j=1：S[1]=b，P[1]=b：相等，i=2，j=2；
- i=2，j=2：S[2]=c，P[2]=c：相等，i=3，j=3；
- i=3，j=3：S[3]=a，P[3]=a：相等，i=4，j=4；
- i=4，j=4：S[4]=b，P[4]=b：相等，i=5，j=5；
- i=5，j=5：S[5]=c，P[5]=d：不相等，触发 j 回退；j = next[j-1] = next[4] = 2（核心：利用 next 数组回退，而非重置为 0）；
- i=5，j=2：S[5]=c，P[2]=c：相等，i=6，j=3；
- i=6，j=3：S[6]=a，P[3]=a：相等，i=7，j=4；
- i=7，j=4：S[7]=b，P[4]=b：相等，i=8，j=5；
- i=8，j=5：S[8]=d，P[5]=d：相等，i=9，j=6；此时 j=m=6（模式串全部匹配完成），匹配成功；起始索引 = i - m = 9 - 6 = 3；
动图演示
3. C++ 代码实现
// 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 数组的存储空间。
1. 时间复杂度
- next 数组生成：遍历模式串一次，长度为 m。内层 while 循环中，j 的回退总次数不超过 j 的前进总次数，因此内层循环总操作数为 O(m)，整体生成 next 数组的时间复杂度为 O(m)。
- KMP 核心匹配：遍历主串一次，长度为 n。同理，内层 while 循环中 j 的回退总次数不超过 j 的前进总次数，内层循环总操作数为 O(m)，整体匹配的时间复杂度为 O(n)。
- 算法总时间复杂度：O(n + m)，线性时间复杂度，远优于暴力匹配的 O(n*m)。
2. 空间复杂度
KMP 算法需要额外存储 next 数组，数组长度为模式串长度 m，因此空间复杂度为 O(m)。
六、KMP 算法的应用场景
KMP 算法作为经典的线性字符串匹配算法，在工程中应用广泛，典型场景包括：
- 文本编辑器的查找功能（如 Notepad++ 的'查找'）；
- 编译器的词法分析（匹配关键字、标识符）；
- 生物信息学（DNA 序列、蛋白质序列的匹配）；
- 网络协议解析（匹配固定的协议字段）；
- 面试高频考点（字符串匹配类题目必问，如 LeetCode 28. 找出字符串中第一个匹配项的下标）。
总结
KMP 算法的核心是'利用已匹配信息，避免重复比较'，而 next 数组是实现这一思想的关键，记住以下 3 个核心点，就能彻底掌握 KMP：
- 最长公共前后缀：next 数组的本质，是模式串每个位置的最长相等真前后缀长度；
- 主串指针不回溯：KMP 的核心改进，仅通过模式串指针 j 的回退实现匹配；
- next 数组的迭代生成：通过前缀指针 j 和后缀指针 i 的遍历，结合回退逻辑，线性时间生成 next 数组。
