核心逻辑与数学原理
KMP 算法的核心任务是在 $O(N + M)$ 时间复杂度内实现单模式串在文本串中的匹配，打破暴力匹配 $O(NM)$ 的固有上限。其底层数学基石是前缀函数（Prefix Function），在竞赛源码中常定义为 $next$ 数组。
1. 前缀函数的数学定义
对于长度为 $M$ 的字符串 $P$，其前缀函数 $next[i]$ 表示子串 $P[0 \dots i]$ 的最长相等真前缀与真后缀的长度。集合表述如下：
$$next[i] = \max \big\{ k \big| 0 \le k < i+1 \text{ and } P[0 \dots k-1] == P[i-k+1 \dots i] \big\}$$
若该集合为空，则 $next[i] = 0$。
2. 失配状态转移的收敛性证明
当文本串字符 $S[i]$ 与模式串字符 $P[j]$ 发生失配时，传统算法将 $i$ 回溯。KMP 保持 $i$ 不动，将 $j$ 转移至 $next[j-1]$。
证明：已知 $P[0 \dots j-1] == S[i-j \dots i-1]$。若存在一个更短的匹配滑块长度 $k$，使得新的前缀能够对接当前后缀，则必须满足 $P[0 \dots k-1] == P[j-k \dots j-1]$。根据前缀函数定义，最大的 $k$ 严格等于 $next[j-1]$。由于 $next[j-1] < j$，转移状态单调递减，迭代必然在有限步内收敛至 $0$。
状态设计与算法推导
1. 前缀函数 $next$ 数组的递推
假设已知 $next[0 \dots i-1]$。现推导 $next[i]$ 的值。令 $j = next[i-1]$。
- 情况一：若 $P[i] == P[j]$，则当前匹配能够向右延伸一位，直接状态转移：
$$next[i] = j + 1$$
- 情况二：若 $P[i] \neq P[j]$，说明当前长度的真前缀无法延伸。此时必须缩短查找范围，跳转至更短的相等真前后缀位置，令 $j = next[j-1]$，重复检查直至 $P[i] == P[j]$。
- 边界：若 $j$ 一直回溯至 $0$ 且依然 $P[i] \neq P[0]$，则 $next[i] = 0$。
2. 模式匹配状态机
将模式串 $P$ 视为一个有限状态自动机，状态值为当前成功匹配的字符数 $j$。对于文本串的每个字符 $S[i]$：
- 若 $S[i] \neq P[j]$ 且 $j > 0$，状态沿失配指针连续回溯：
j = next[j - 1]。 - 若 $S[i] == P[j]$，状态向高位推进：
j++。 - 若 $j == M$，说明成功命中完整模式串，记录答案位置 $i - M + 1$，随后状态强制转移至
j = next[j - 1]以继续匹配后续重叠子串。
C++ 标准源码（NOIP风格）
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// 高效输入函数，处理常规字符串读入
void fast_io() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
const int MAXM = 1000005;
int nxt[MAXM]; // 避开 C++ 某些头文件中的全局关键字 next，硬核重命名为 nxt
// 严格基于 0 下标递推计算前缀函数
void get_next(const string& p, int m) {
nxt[0] = 0; // 长度为 1 的子串无真前后缀，必然为 0
int j = 0; // j 始终代表当前待比较的前缀字符下标，同时也是前一位置的 nxt 值
for (int i = 1; i < m; ++i) {
while (j > 0 && p[i] != p[j]) {
j = nxt[j - 1]; // 致命踩坑点：失配时必须回溯到 nxt[j-1] 而不是 nxt[j]
}
if (p[i] == p[j]) {
j++;
}
nxt[i] = j;
}
}
// KMP 主匹配过程
void kmp_search(const string& s, const string& p) {
int n = s.length();
int m = p.length();
get_next(p, m);
int j = 0; // 模式串的匹配指针
for (int i = 0; i < n; ++i) {
while (j > 0 && s[i] != p[j]) {
j = nxt[j - 1]; // 文本串与模式串失配，自适应转移状态，i 指针绝不回溯
}
if (s[i] == p[j]) {
j++;
}
if (j == m) {
// 成功在文本串中匹配到模式串，输出起始标准下标（1-based 风格常见于 NOIP 评测）
cout << i - m + 2 << "\n";
j = nxt[j - 1]; // 致命踩坑点：匹配成功后为了寻找重叠的下一个目标，必须强制转移状态
}
}
}
int main() {
fast_io();
string s, p;
if (cin >> s >> p) {
kmp_search(s, p);
int m = p.length();
for (int i = 0; i < m; ++i) {
cout << nxt[i] << (i == m - 1 ? "" : " ");
}
cout << "\n";
}
return 0;
}NOIP 实战避坑指南
1. 全局变量命名冲突与编译流产
在线下 Linux 环境下使用 g++ -O2 编译时，若引入了某些标准库，全局声明 int next[MAXN]; 会与 <algorithm> 或内建命名空间中的标准迭代器算子 std::next 发生代数命名冲突。这会导致编译器抛出难以辨识的符号重载错误。必须在竞赛中将数组严格命名为 nxt 或 nxt_arr。
2. 失配索引越界与死循环
在 while (j > 0 && p[i] != p[j]) 循环内部，跳转语句若写为 j = nxt[j]; 将直接引发逻辑灾难。因为当 j 处的字符失配时，应当查询的是已经匹配成功的子串 $P[0 \dots j-1]$ 的最长公共前后缀。若写成 nxt[j]，不仅丢失了数学正确性，更可能由于 nxt[j] == j 的恶性数据陷入无限死循环，或在 $j = M$ 时越界触发 RE。
3. 下标 0-based 与 1-based 混用导致状态断层
KMP 算法的实现极度依赖下标边界。若在读取 string 时使用 0 下标，而 next 数组的转移逻辑借鉴了某些教科书上的 1 下标算法（如 nxt[j] = nxt[nxt[j]] 且初始置 nxt[0] = -1），会导致边界索引出现 $\pm 1$ 的物理偏离，状态机将彻底失去高位拦截作用，在评测机上表现为大面积 WA。
经典 NOIP/洛谷 真题
1. 洛谷 P3375 【模板】KMP 字符串匹配
- 题意描述：给出两个字符串 $S_1$ 和 $S_2$，求 $S_2$ 在 $S_1$ 中所有出现的起止位置，并输出 $S_2$ 的前缀函数数组。
- 问题本质：纯粹的标准 KMP 算法工业级落地。
- 核心解题思路：如标准源码所示，先通过 $O(M)$ 复杂度的单串自我规约递推求出整个
nxt状态机，再用该状态机去对冲文本串 $S_1$。整个算法只包含线性的双指针单向平移，时间复杂度严格锁死在 $O(N + M)$，空间复杂度仅为 $O(M)$。
2. 洛谷 P2375 [NOI2014] 动物园
- 题意描述：对于一个字符串 $S$，定义 $num[i]$ 表示既是 $S[0 \dots i]$ 的相等真前后缀，且长度不超过该子串总长一半的字符串个数。求整个字符串所有位置的 $(num[i] + 1)$ 的累乘积模 $10^9 + 7$。
- 问题本质：前缀函数树（$next$ 树）的拓扑深度挖掘。
- 核心解题思路：如果直接沿着
nxt数组暴力向前回溯查找长度小于等于一半的位置，时间复杂度会退化为 $O(N^2)$ 导致TLE。核心破局点在于：KMP 的nxt指针实际上构成了一棵向根节点汇聚的树形拓扑结构（每个节点 $i$ 的父亲是 $nxt[i-1]$）。$num[i]$ 的本质就是求在该树上当前节点的祖先链中，值小于等于 $\lfloor \frac{i+1}{2} \rfloor$ 的节点个数。我们可以维护一个类似于 KMP 匹配的双指针num_j，在推进i的同时，让num_j保持在不越过一半的最高合法位置。利用双指针的单向不回溯性，将时间复杂度硬核压制在 $O(N)$。