KMP算法

关于 KMP 算法

核心思想

KMP 算法（Knuth-Morris-Pratt）主要用于在一个长字符串（主串 haystack）中查找一个短字符串（模式串 needle）的出现位置 。它的核心思想是利用模式串自身的特点，避免不必要的回溯，从而提高匹配效率。

主要讲解 KMP 算法的两个关键部分：生成 next 数组（前缀表）和使用 next 数组进行匹配。

---

生成 next 数组

我们要求模式串的 next 数组，其实求的就是在每个位置的最长公共前后缀的长度。

定义两个指针，l 是前缀指针，r 是后缀指针。我们要求模式串的 next 数组。

以 aaab 为例，令 l=0, r=1，然后开始遍历。

在 for 循环中，right 从 1 开始，left 从 0 开始 。

在 while 循环里，如果 left 位置的字符不等于 right 位置的字符，left 指针会回退到上一个匹配过的位置，即 left = next[left - 1]。这个回退操作是核心，它利用的是“相同前后缀的相同前后缀”思想，而不是简单地回到 0 。

如果 left 位置的字符与 right 位置的字符相等，left 指针就向右移动一位。

当循环结束时，next 数组就计算完毕了。

for (int right = 1, left = 0; right < needleLength; right++) {
    // 定义好两个指针right与left
    // 在for循环中初始化指针right为1，left=0,开始计算next数组，right始终在left指针的后面
    while (left > 0 && needle.charAt(left) != needle.charAt(right)) {
        // 如果不相等就让left指针回退，到0时就停止回退
        left = next[left - 1];//进行回退操作；
    }
    if (needle.charAt(left) == needle.charAt(right)) {
        left++;
    }
    next[right] = left;
}
// 循环结束的时候，next数组就已经计算完毕了


class Solution {
    public int strStr(String haystack, String needle) {
        int needleLength = needle.length();
        if (needleLength == 0) return 0;
//        当needle是空字符串时，返回0

        int[] next = new int[needleLength];
//        定义好next数组

        for (int i = 0,j=0; i <haystack.length() ; i++) {

            while (j>0&&haystack.charAt(i)!=needle.charAt(j)){
                j=next[j-1];
            }
            if (haystack.charAt(i)==needle.charAt(j)){
                j++;
            }
            if (j==needleLength) return i-needleLength+1;
        }
        return -1;


    }
}