题解 | kmp算法

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算模板串S在文本串T中出现了多少次
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
     public static int kmp(String S, String T) {
        // write code here
        int num=0;
        int[] next=getNext(S);
        int i=0,j=0;
        while(j<S.length()&&i<T.length()){
            if(j==-1||S.charAt(j)==T.charAt(i)){
                i++;
                j++;
            }else{
                j=next[j];
            }
            if(j>S.length()-1){
                num++;
                j=next[j];
            }
        }
        return num;
    }
    public static int[] getNext(String S){
        int[] next =new int[S.length()+1];
        int i=0;
        int j=-1;
        next[0]=-1;
        while(i<S.length()){
            if(j==-1||S.charAt(i)==S.charAt(j)){
                i++;
                j++;
                next[i]=j;
            }else{
                j=next[j];
            }
        }
        return next;
    }


}