问题与动机
KMP（Knuth-Morris-Pratt）算法在主串（文本）中查找模式串，复杂度 O(n + m)。暴力匹配每次失配都要把主串指针回溯、模式串指针归零，导致大量重复比较；KMP 的核心贡献是：主串指针永不回溯，失配时只移动模式串指针——移动多少由预处理好的 next 数组决定。
next 数组（部分匹配表）
对模式串 P，next[i] 表示 P[0..i-1]（不含 P[i] 的前缀）的最长相同前后缀长度。例如模式串 P = "ABABCABAB"：
next = [0, 0, 1, 2, 0, 1, 2, 3, 4]
含义：失配时模式串指针回退到的位置。它代表”当前已匹配的后缀里，还能作为前缀继续匹配的最长长度”——这样就能安全地跳过必然失配的比较。
构建 next 数组（O(m)）
vector<int> computeNext(const string& p) {
int m = p.size();
vector<int> next(m, 0);
for (int i = 1, j = 0; i < m; i++) {
while (j > 0 && p[i] != p[j]) j = next[j - 1];
if (p[i] == p[j]) j++;
next[i] = j;
}
return next;
}
指针 i 从 1 开始，j 记录”已匹配的相同前后缀长度”：字符相等则 j+1；不等则沿 next 回退，直到相等或 j 归零。这是 KMP 里最容易写错的部分——回退循环里 j = next[j-1] 而非 j = 0。
匹配过程（O(n)）
int kmpSearch(const string& s, const string& p) {
int n = s.size(), m = p.size();
if (m == 0) return 0;
vector<int> next = computeNext(p);
for (int i = 0, j = 0; i < n; i++) {
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;
}
主串指针 i 只前进，失配时模式串指针 j 按 next 跳转；找到完整匹配后如需继续找下一个，做 j = next[j-1] 即可（重叠匹配也能找全）。
示例走查
主串 S = "ABABDABACDABABCABAB"，模式串 P = "ABABCABAB"：
i=0..3: A B A B 全部匹配，j=4
i=4: S[4]='D' != P[4]='C'，j = next[3] = 2
S[4]='D' != P[2]='A'，j = next[1] = 0
S[4]='D' != P[0]='A'，i 前进
i=5..8: 匹配 ABAB，j=4
i=9: S[9]='B' != P[4]='C'，j = next[3] = 2
S[9]='B' != P[2]='A'，j = next[1] = 0
S[9]='B' != P[0]='A'，i 前进
i=10..17: 完整匹配 ABABCABAB，j=8==m，返回 i-m+1 = 10
可以看到：失配时主串指针从未回退，全靠 next 数组把模式串”平移”到正确位置，因此整体是线性的。
复杂度与总结
- 构建 next：O(m)；匹配：O(n)；总复杂度 O(n + m)；
- 相比暴力 O(n·m)，避免了主串回溯带来的重复比较；
- next 数组的思想（利用已匹配信息、前缀后缀复用）是理解 AC 自动机、Z 函数等进阶字符串算法的基础。
