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