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;
    }
}

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