KMP 算法是一种高效的字符串匹配方法，用于在主文本中查找模式串的位置。该算法避免了传统暴力匹配中不必要的回溯操作，从而提升了整体性能。

在进行字符串匹配时，若当前字符不匹配，KMP 利用已知的部分匹配信息决定模式串应向右滑动多少位，而不是简单地逐位移动。这种方式显著减少了重复比较的次数。

基本思想

考虑在字符串 T 中查找模式串 P 的过程。假设当前比较到 T[i] 和 P[j] 不一致：

• 传统做法是将模式串向右移动一位，并重置 j=0。
• KMP 做法则是根据预先计算好的"部分匹配表"（通常称为 next 数组），仅调整 j 的位置，保持 i 不变。

构建 next 数组

next 数组记录的是每个位置 j 对应的最长公共前后缀长度。具体来说，next[j] 表示当 P[j] 与 T[i] 失配时，j 应该跳转到的新位置。

构造 next 数组的过程本质上是在模式串自身内部查找最长相等前后缀：

public static int[] buildNextArray(String pattern) {
    char[] p = pattern.toCharArray();
    int[] next = new int[p.length];
    next[0] = -1;
    int prefixIndex = -1;
    int suffixIndex = 0;

    while (suffixIndex < p.length - 1) {
        if (prefixIndex == -1 || p[prefixIndex] == p[suffixIndex]) {
            prefixIndex++;
            suffixIndex++;
            // 防止连续相同字符导致无效跳跃
            if (p[suffixIndex] == p[prefixIndex]) {
                next[suffixIndex] = next[prefixIndex];
            } else {
                next[suffixIndex] = prefixIndex;
            }
        } else {
            prefixIndex = next[prefixIndex];
        }
    }

    return next;
}

KMP 匹配函数实现

借助上述 next 数组，可编写完整的 KMP 匹配逻辑：

public static int kmpSearch(String text, String pattern) {
    char[] t = text.toCharArray();
    char[] p = pattern.toCharArray();
    int textIndex = 0;
    int patternIndex = 0;
    int[] next = buildNextArray(pattern);

    while (textIndex < t.length && patternIndex < p.length) {
        if (patternIndex == -1 || t[textIndex] == p[patternIndex]) {
            textIndex++;
            patternIndex++;
        } else {
            patternIndex = next[patternIndex];
        }
    }

    return patternIndex == p.length ? textIndex - patternIndex : -1;
}

相较于朴素匹配算法，KMP 最大的改进在于避免了文本指针的回退，使得时间复杂度降低至 O(n + m)，其中 n 是文本长度，m 是模式串长度。

需要注意的一个优化点是：当模式串中存在连续相同的字符时，直接使用基础版 next 可能会导致不必要的比较。因此，在实际应用中推荐采用优化后的版本以提升效率。