力扣 (opens new window) KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配。 next数组就是一个前缀表，next[i] 表示 i（包括i）之前最长相等的前后缀长度，用来做回退的，记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。（待匹配的那个小串） 前缀：指不包含最后一个字符的所有以第一个字符开头的连续子串。 后缀：指不包含第一个字符的所有以最后一个字符结尾的连续子串。

构建next数组

假设有匹配串 aaabbab，我们来看看对应的 next 是如何被构建出来的。 这就是整个 next 数组的构建过程，时空复杂度均为O(m)。

代码实现

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) return 0;
        int[] next = new int[needle.length()];
        getNext(next, needle);
        
// 利用next数组进行跳转匹配，不再需要回退haystack的指针i
        int j = 0;
        for (int i = 0; i < haystack.length(); i++) {
            while (j > 0 && needle.charAt(j) != haystack.charAt(i))//注意是循环！
                j = next[j - 1];
            if (needle.charAt(j) == haystack.charAt(i)) 
                j++;
            if (j == needle.length()) 
                return i - needle.length() + 1;
        }
        return -1;

    }
    
//前缀表（不减一）    
//构造next数组，next数组中的元素表示当前两个元素不匹配时，指针要跳转的位置
    private void getNext(int[] next, String s) {
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < s.length(); i++) {  //i从1开始
            while (j > 0 && s.charAt(j) != s.charAt(i))//注意是循环！
                j = next[j - 1];//不相等，找前一位的对应的回退位置（因为数组-1计数，长度会使自动到下一匹配位）
            if (s.charAt(j) == s.charAt(i))
                j++;//相等i j同时前进
            next[i] = j; //长度，所以取+1后的
        }
    }
}

时间复杂度：n 为原串的长度，m 为匹配串的长度。复杂度为O(m+n)。 空间复杂度：构建了 next 数组。复杂度为O(m)。