KMP中next最长公共前缀

力扣题目链接

在构造next数组的时候，这一块是最难理解的部分。

            while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) {
                j = next[j];
            }

next 里面放的是haystack中第 j 和数与，next第i个数不匹配的时候，跳转到下标为i = next[i] 的位置。继续让 j 与 next 中 index = next[i] 个数进行匹配匹配。
不必让两个字符串都重新开始，从而将时间时间复杂度从O(m*n)降低到O(m+n)。

next 数组里面放的是当第index数不匹配的时候，应该跳转到的下标。也是最长公共前后缀个数减一

  public void getNext(int[] next, String s) {
        
        int j = -1;
        next[0] = j;
        for (int i = 1; i < s.length(); i++) {// 注意i从1开始
            while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) {
                j = next[j];
            }
            if (s.charAt(i) == s.charAt(j + 1)) {
                j++;
            }
            next[i] = j;
        }
    }

    public int strStr(String haystack, String needle) {
        
        if (needle == null || needle.length() == 0 || haystack == null || haystack.length() == 0) {
            return 0;
        }
        int[] next = new int[needle.length()];
        getNext(next, needle);
        int j = -1;
        for (int i = 0; i < haystack.length(); i++) {// 注意i从1开始
            while (j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)) {
                j = next[j];
            }
            if (haystack.charAt(i) == needle.charAt(j + 1)) {
                j++;
            }
            if (j == needle.length() - 1) {
                return i - needle.length() + 1;
            }
        }
        return -1;
    }

    public void getNext(int[] next, String s) {

        
        for (int i = 1, j = 0; i < s.length(); i++) {// 注意i从1开始
            while (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = next[j - 1];
            }
            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
    }

    public int strStr(String haystack, String needle) {
        
        if (needle == null || needle.length() == 0) {
            return 0;
        }
        int[] next = new int[needle.length()];
        getNext(next, needle);
        int j = 0;
        for (int i = 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 == needle.length()) {
                return i - needle.length() + 1;
            }
        }
        return -1;
    }