Java KMP

对原生kmp做个改造

主要两点：

1. next数组多算一格
2. kmp匹配时，如果完全匹配上，则ans计数+1， 并让模式串移动到next[ti]位置

    public int kmp (String S, String T) {
        // write code here
        int[] next = getNext(S);
        char[] str =T.toCharArray();
        char[] t = S.toCharArray();
        int si =0;
        int ti =0;

        int ans =0;
        while(si < str.length){
            if(ti==-1 || str[si] == t[ti]){
                si++;
                ti++;
            }else{
                ti = next[ti];
            }
            if(ti == t.length){  //改造2
                ans++;
                ti=next[ti];
            }
        }
        return ans;
    }

    public int[] getNext(String S){
        char[] str= S.toCharArray();
        int[] next=  new int[str.length+1]; //改造1
        next[0]=-1;
        next[1] = 0;
        int cur=2;
        int x = next[cur-1];
        while(cur<=str.length){
            if(x==-1 || str[cur-1]==str[x]){
                next[cur++] = ++x;
            }else{
                x=next[x];
            }
        }
        return next;
    }