KMP字符串匹配算法详解：掌握变量指针回溯的避坑技巧-java教程-PHP中文网

kmp算法核心是利用最长相同前后缀实现主串指针不回溯；next[j]表示模式串p[0..j-1]的最长真前缀与真后缀相等长度，失配时j跳至next[j]，i保持不变，从而避免暴力回退。

kmp算法的核心不是暴力回退，而是利用已匹配部分的“最长相同前后缀”跳过无效比较。关键在next数组的构建与使用——它决定了主串指针不回溯、模式串指针如何安全回跳。

next[j] 表示模式串 P[0..j-1] 的最长真前缀（不等于自身）与真后缀相等的长度，也就是当 P[j] 失配时，模式串应跳到的位置索引（即 P[next[j]] 继续比较）。注意：不同教材定义略有差异（有的存长度，有的存下标），统一按下标偏移理解更不易错。

若采用 next[j] = k 表示失配时 P[j] 应与 P[k] 对齐，则 next[0] 必须设为 -1（表示无可用前缀，直接右移）
构建时用双指针 i（当前待求位置）、j（前缀末尾位置），初始 j = -1；每次比较 P[i-1] 和 P[j]，相等则 j++，next[i] = j；否则 j 回退至 next[j]
常见错误：把 next[1] 初始化为 0 后，对 j=0 时未做边界防护，导致数组越界或逻辑断裂

暴力匹配中主串指针频繁回滚（如从 i 回到 i−j+1），而KMP中主串指针 i 只进不退。失配时仅调整模式串指针 j = next[j]，继续用当前 i 与新 P[j] 比较。这要求 next 数组必须准确反映“已知匹配段”的内部结构。

例如模式串 "ababaca"，匹配到第5位（0-indexed，即 'c'）失配时，已成功匹配 "ababa"；其最长相同前后缀是 "aba"（长3），所以 j 从 5 → 3，i 不动，接着比 P[3]=='b' 和 S[i]
若 next 值算小了，会多做比较；算大了，则跳过可能匹配，导致漏解
实际编码中建议在 while 循环内加 j >= 0 判断，避免 j = next[j] 后变为负数却未终止

next 构建本身也是个 KMP 过程：用模式串自己匹配自己。这里 j 的回退逻辑和主匹配一致，但初学者常在此处混淆“j 是前缀指针”而非“当前字符下标”，从而写错递推条件。

正确写法：while (j >= 0 && p[i] != p[j]) j = next[j]; —— 注意是 p[i] 和 p[j] 比，不是 p[i] 和 p[i-1]
错误典型：把 j = next[j] 写在 while 外、或漏掉 j >= 0 判断，导致无限循环或崩溃
调试技巧：手动算 small case 的 next，如 "aaaa" → [-1,0,1,2,3]，"abcab" → [-1,0,0,0,1,2]，对照代码输出逐项验证