28. 实现 strStr()

在一个串中查找是否出现过另一个串，这是KMP的看家本领

说到KMP，先说一下KMP这个名字是怎么来的，为什么叫做KMP呢。

因为是由这三位学者发明的：Knuth，Morris和Pratt，所以取了三位学者名字的首字母。所以叫做KMP

KMP主要应用在字符串匹配上。

KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。

所以如何记录已经匹配的文本内容，是KMP的重点，也是next数组肩负的重任。

写过KMP的同学，一定都写过next数组，那么这个next数组究竟是个啥呢？

next数组就是一个前缀表（prefix table）。

前缀表有什么作用呢？

前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配，注意这里说的是被寻找的对象而不是探寻的那个长长的字符串

class Solution {
    public int strStr(String haystack, String needle) {
        if(needle.length()==0){
            return 0;
        }
        int[] next = nexttable(needle);
        int j = -1;
        for(int i = 0; i < haystack.length(); i++){
            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 int[] nexttable(String needle){
        int len = needle.length();
        int j = -1;
        int[] result = new int[len];
        result[0] = j;
        for(int i = 1; i < len; i++){
                while( j >= 0 && needle.charAt(i) != needle.charAt(j+1)){
                    j = result[j];
                }
                if (needle.charAt(i) == needle.charAt(j+1)) j += 1;
                result[i] = j;
        }
        return result;
    }
}

决定放过我自己 明天再看看

 459.重复的子字符串  （本题可以跳过）

本题算是KMP算法的一个应用，不过 对KMP了解不够熟练的话，理解本题就难很多。 

我的建议是 KMP和本题，一刷的时候 ，可以适当放过，了解怎么回事就行，二刷的时候再来硬啃

题目链接/文章讲解/视频讲解：https://programmercarl.com/0459.%E9%87%8D%E5%A4%8D%E7%9A%84%E5%AD%90%E5%AD%97%E7%AC%A6%E4%B8%B2.html

再一次强调了什么是前缀，什么是后缀，什么又是最长相等前后缀。

前缀：指不包含最后一个字符的所有以第一个字符开头的连续子串。

后缀：指不包含第一个字符的所有以最后一个字符结尾的连续子串。

然后针对前缀表到底要不要减一，这其实是不同KMP实现的方式，我们在KMP精讲 (opens new window)中针对之前两个问题，分别给出了两个不同版本的的KMP实现。

其中主要理解j=next[x]这一步最为关键

复习双指针算法