kmp比暴力匹配快是因为避免主串指针回退，利用next数组实现o(n+m)时间复杂度；next构建需双指针正确回退，搜索时失配应j=next[j-1]而非归零，注意边界、空串及数组大小等隐性坑。
为什么 kmp_search 比暴力匹配快？
因为 KMP 避免了主串指针回退。暴力匹配中，每次失配都要把主串位置往回挪，最坏 O(n×m)；KMP 用 next 数组（也叫 lps）记录模式串自身最长公共前后缀长度，失配时只移动模式串指针，主串指针一路向前，时间复杂度稳定在 O(n + m)。
关键点在于：next[j] 表示 pattern[0..j] 的最长相等真前后缀长度。它决定了失配后 j 应该跳到哪，而不是归零。
next 数组怎么构建才不出错？
常见错误是初始化不当或边界判断松散，导致 next[0] = 0 没设、j 越界、或循环中 j 没及时回退。正确做法是双指针推进：
- 令
i = 1（从第二个字符开始），j = 0（前缀末尾） - 若
pattern[i] == pattern[j]，则next[i++] = ++j - 否则若
j > 0，令j = next[j-1]继续尝试匹配；若j == 0，则next[i++] = 0
注意：有些实现用 next[0] = -1 并调整比较逻辑，但标准教材和多数工程代码用 next[0] = 0 更直观，也更易与搜索主循环对齐。
立即学习“C++免费学习笔记（深入）”；
KMP 搜索主循环里 j 什么时候重置？
不是失配就直接 j = 0——那是暴力法。KMP 中，失配时应利用 next 回退：j = next[j-1]（前提是 j > 0）。只有当 j == 0 且仍不匹配，才说明当前主串位置无法启动匹配，此时 i++ 继续推进。
典型错误写法：if (s[i] != p[j]) j = 0; —— 这完全丢掉了 KMP 的加速能力。
正确片段节选：
int i = 0, j = 0;
while (i < n) {
if (s[i] == p[j]) {
i++; j++;
if (j == m) return i - m; // 找到
} else if (j > 0) {
j = next[j-1];
} else {
i++;
}
}
实际使用时要注意哪些隐性坑？
字符串索引是否越界、next 数组大小是否为 m（模式串长）、空模式串如何处理，这些都容易引发崩溃或逻辑错误。
- 若
m == 0，应直接返回0或按需求定义行为（如 C++std::string::find对空串返回0） -
next数组必须用std::vector<int>(m)</int>分配，不能只开m-1个元素 - C++ 中
std::string的operator[]不检查边界，调试时建议先加assert(i - 若需所有匹配位置，不要在找到后立即
return，而是记录i - m，然后执行j = next[j-1]继续找重叠匹配（如模式"aa"在"aaaa"中应匹配位置 0、1、2）
真正难的不是写出能跑通的版本，而是让 next 构建和主循环中 j 的跳转逻辑在所有边界输入下保持一致——比如全相同字符、单字符、前缀即后缀等情况，一不留神就会漏掉一次 next 回退。
