题解 | #kmp算法#

public int kmp (String S, String T) {
        // write code here
        int cnt=0;
        int i=0;
        int j=0;
        int[] next=getNext(S);
        while(j<T.length()){
            while(i>0 && S.charAt(i)!=T.charAt(j)){
                i=next[i-1];
            }
            if(S.charAt(i)==T.charAt(j)){
                i++;
                j++;
            }
            if(i==S.length()){
                cnt++;
                i=next[i-1];
            }
        }
        return cnt;
    }
    //获取next数组
    public int[] getNext(String S){
        int[] next=new int[S.length()];
        next[0]=0;
        for(int i=1,j=0;i<S.length();i++){
            while(j>0 && S.charAt(i)!=S.charAt(j)){
                j=next[j-1];
            }
            if(S.charAt(i)==S.charAt(j)){
                j++;
            }
            next[i]=j;
        }
        return next;
    }