java String kmp算法 LeetCode 28题解 字符串匹配

做到LeetCode第28题，看完题干就知道是考kmp算法，愣是想不起来kmp算法怎么写了，把四年前的知识还给老师了，复习了复习，码出来代码以后留着复习用。

原理：nexts数组是kmp算法核心，每一位的值用来代表前面有多少位是重复的，可以从这个值来继续判断（数组下标从0开始，例如前5为是重复的，则可以从下标为5继续判断，因为这是第6个元素），同时意思是，如果要匹配的字符某位和当前模板某位查找不匹配（失败）则意味着要回退到之前匹配过的位置，也就是可以从这个值开始继续遍历模板，之前的不用再看，因为前面的重复。

举个栗子：

模板字符为：      ababcababe

则nexts数组为：-1001201234

如何求nexts数组：规定第一位为-1，第二位为0；从第三位开始，当前数据下标为index，nexts数组index-1位置的值为count，count即为i-1位置最长公共前缀，不包含当前为index-1。如果index-1位字符（上一位字符）和count位字符（最长公共前缀的下一个位字符） 相等，则表示上一位也重复，那么count++，记录在nexts[index]位。如果不一样，则取nexts[index-1]位置的值，也就是刚刚记录的count，作为下标，取到nexts[count]作为新的count，这个操作表示上一位（index-1）不再是公共前缀里一员，需要倒退到上一个字符的最长公共前缀的后一位（数组下标：nexts[index-1]）来进行匹配是否相等。此时会想：为啥跳到nexts[index-1]这个值的位置来开始判断？正如刚才红字所说，因为index-1这一位不再一样，且值count为index-1位的字符有多少位是相等的最长前缀，说明可以跳到第count位（数组都是从0开始的）上开始判断是否一样，毕竟前count-1位都是一样的。如果还不一样则继续取到新的count值，循环判断。

这块比较绕，自己多看几遍，找几个例子写写画画就懂了。

如何字符串匹配：当然是两个游标，判断这两个字符一样就继续下一位。如果不一样了，就要取nexts[index2]的值作为新的index2，碰到nexts[index2]的值为-1的时候，说明第一位也不一样了，就要移动index1,把index1++。

public class Solution {

    public static int strStr(String haystack, String needle) {
        if(needle.length()<1) return 0;
        if(haystack==null||haystack.length()<1||needle==null) return -1;
        int[] nexts = getNexts(needle);
        int index1 = 0;
        int index2 = 0;
        while(index1<haystack.length()&&index2<needle.length()){
            if(haystack.charAt(index1) == needle.charAt(index2)){
                index1++;
                index2++;
            }else if (nexts[index2]==-1){
                index1++;
                index2=0;
            }else {
                index2=nexts[index2];
            }
        }
        if(index2==needle.length()){
            return index1-index2;
        }
        return -1;
    }

    public static int[] getNexts(String needle){
        if(needle.length()==1){
            return new int[]{-1};
        }
        int[] nexts = new int[needle.length()];
        nexts[0]=-1;
        nexts[1]=0;

        int count=0;
        int index=2;
        while(index<needle.length()){
            if(needle.charAt(index-1) == needle.charAt(count)){
                nexts[index++]=++count;
            }else if(count>0){
                count=nexts[count];
            }else {
                nexts[index++]=0;
            }
        }

        return nexts;
    }

    public static void main(String[] args) {
        String needle = "ll";
        String haystack = "hello";
        int[] nexts = getNexts(needle);
        for(int i=0;i<nexts.length;i++){
            System.out.print(nexts[i]+" ");
        }
        System.out.println();
        System.out.println(strStr(haystack,needle));
    }
}