next数组算错会导致KMP匹配失效，因其跳转完全依赖next值：偏大会跳过合法匹配，偏小则退化为暴力回溯；常见错误包括next[0]初值混用、j维护不当、边界未处理。
为什么 next 数组算错会导致匹配直接失效
根本原因在于：KMP 的跳转完全依赖 next 数组。如果某一位的 next[j] 值偏大（比如该是 1 却写成 2），匹配失败时会跳过本该重试的位置，漏掉合法匹配；如果偏小（比如该是 2 却写成 0），则退化为暴力回溯，失去 KMP 的线性优势。
常见错误包括：next[0] = -1 或 0 混用、循环中未正确维护 j（前缀末尾索引）、比较时用 pattern[i] == pattern[j] 却没处理 j == -1 的边界。最稳妥的做法是统一用 next[0] = -1，并让 j 始终表示「当前已匹配前缀的下一个位置」。
实操建议：
- 初始化
next[0] = -1，i = 0，j = -1 - 主循环条件用
i ，不是i - 当
j == -1 || pattern[i] == pattern[j]时才推进；否则只更新j = next[j] - 每次成功匹配后，
next[++i] = ++j（注意是先自增再赋值）
如何写出不依赖 std::string 的纯 C 风格 KMP 匹配函数
很多嵌入式或性能敏感场景要求零 STL 依赖。这时需手动管理字符数组和长度，且避免 std::string::find 这类黑盒调用——你无法控制其内部是否真用 KMP，也不方便调试 next。
立即学习“C++免费学习笔记（深入）”；
关键点在于：匹配主循环必须严格 O(n)，不能在每次失配时从头比对。核心逻辑是用 next 数组驱动模式串指针 j 跳转，而非文本串指针 i 回退。
实操建议：
- 输入用
const char* text和const char* pattern，配合显式长度int t_len,int p_len - 匹配循环中，仅当
j == p_len才找到一次匹配，此时记录位置并执行j = next[j-1]继续找重叠匹配 - 避免在循环内调用
strlen()—— 它是 O(n) 的，会让整体退化 - 若需支持空模式串，提前返回 0 或特殊约定（如定义空串在每个位置都匹配）
next 数组优化版（nextval）到底省了什么
标准 next 在某些模式下仍会做无意义比较。例如模式串 "aaab"，next[3] = 2，但 pattern[3] == 'b'，而 pattern[2] == 'a'，所以失配时跳到 j = 2 后立刻再次失配。优化版 nextval 提前把这种「跳过去也必然失败」的位置再压缩一次。
本质是：当 pattern[j] == pattern[next[j]] 时，把 nextval[j] = nextval[next[j]]，否则 nextval[j] = next[j]。它不提升最坏时间复杂度，但在重复字符多的模式（如日志关键词、协议字段）中显著减少比较次数。
实操建议：
- 先算出完整
next数组，再单独遍历生成nextval - 注意边界：
next[j] == -1时，nextval[j]必须也为-1，不可访问pattern[-1] - 若模式串极短（
int kmp_search(const char* text, int t_len, const char* pattern, int p_len, const int* nextval) {
if (p_len == 0) return 0;
int i = 0, j = 0;
while (i < t_len && j < p_len) {
if (j == -1 || text[i] == pattern[j]) {
i++; j++;
} else {
j = nextval[j];
}
}
return (j == p_len) ? i - p_len : -1;
}真正容易被忽略的是：nextval 对内存局部性有轻微影响——它把原本连续的 next 数组改成了间接跳转链，现代 CPU 的预取器可能不如原版友好。高频短模式匹配时，不妨实测 next 和 nextval 的 L1d cache miss 率。
