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

        return count;
    }
}