1. KMP 与朴素匹配的复杂度对比中朴素算法最坏 O(n·m)（如 'aaaa...b' 对 'aaaa...a'），KMP 如何通过 next 数组避免回溯降到 O(n+m)？
问题
请对比朴素字符串匹配算法与 KMP 算法的时间复杂度，说明为什么朴素算法最坏情况是 O(n·m)，并解释 KMP 是如何通过 next 数组避免指针回溯从而将复杂度降到 O(n+m) 的？
考察点
- 朴素匹配的失配定位与指针回溯机制
- KMP 中主串指针不回退、模式串指针由 next 数组决定跳跃的核心思想
- next 数组的自匹配（最长公共前后缀）构造
答案
朴素算法在文本串与模式串的每个位置都进行一次完整匹配尝试，当文本形如 'aaaa...b'、模式形如 'aaaa...a'（n 与 m 都很大时）的极端情况下，每次在最后一个字符才失配，共尝试约 n 次、每次比对 m 个字符，总时间 O(n·m)。KMP 的核心改进是：失配时主串指针 i 不回退，而是利用 next 数组把模式串指针 j 跳到下一个可能匹配的位置，继续比较。由于模式串在 j 之前的字符已经与文本匹配，next[j] 表示前缀中与已匹配后缀相同的最大长度，因此跳跃后无需重新比较这些公共部分。这样主串指针 i 单调递增（最多前进 n 次），模式串指针 j 累计最多回退 n 次，总复杂度 O(n+m)。
解析
朴素算法的浪费在于失配后把主串指针和模式串指针同时回退，导致同一位置被反复比较。KMP 的关键洞察是"我们已经知道模式串中已匹配的部分"，通过 next 数组把这个信息保存下来，从而主串指针永不回退。复杂度 O(n+m) 的证明基于摊还分析：j 每次增加源于主串前进，j 每次回退都对应之前一次前进，因此总回退次数 ≤ 总前进次数 = n。
示例代码
public static int kmp(String text, String pattern) {
int n = text.length(), m = pattern.length();
int[] next = buildNext(pattern);
for (int i = 0, j = 0; i < n; i++) {
while (j > 0 && text.charAt(i) != pattern.charAt(j)) j = next[j - 1];
if (text.charAt(i) == pattern.charAt(j)) j++;
if (j == m) return i - m + 1; // 找到
}
return -1;
}
private static int[] buildNext(String p) {
int m = p.length();
int[] next = new int[m];
for (int i = 1, j = 0; i < m; i++) {
while (j > 0 && p.charAt(i) != p.charAt(j)) j = next[j - 1];
if (p.charAt(i) == p.charAt(j)) j++;
next[i] = j;
}
return next;
}