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;
}
}