public static int KMP(String str,String sub) {
        if (str==null || sub==null) return -1;

        int lenStr=str.length();
        int lenSub=sub.length();

        int i=0;
        int j=0;

        int[] next=new int[lenSub];
        getNext(next,sub);

        while (i<lenStr && j<lenSub) {
            if ( str.charAt(i)==sub.charAt(j)) {
                i++;
                j++;
            } else if(next[j]==-1){//j==0;sub中比对的位置已经无法往前跳了
                i++;//str中的i++
            }else {
                j=next[j];
            }
        }
        if (j>=lenSub) {
            return i-j;
        }

        return -1;
    }


    public static void getNext(int[] next,String sub){
        if (sub==null) return;

        next[0]=-1;
        next[1]=0;
        //人为规定-1,0，所以i从2小标开始
        int i=2;
        int k=0;//i=2,i-1=1,1下标是0的值,k也指那个字符跟i-1字符比，相同+1


        while (i<sub.length()) {
            //k=-1时，+1=0；继续i++，
            if (k==-1 || sub.charAt(i-1)==sub.charAt(k)) {
                next[i]=k+1;
                i++;//求下一个i位置
                k++;
            }else {
                k=next[k];//k往前跳

            }
        }
    }

    public static void main(String[] args) {
        System.out.println(KMP("kdjsls","djs"));
        System.out.println(KMP("kdjsls","djsa"));
        System.out.println(KMP("kdjsls","kd"));

    }