题解 | #kmp算法#

import java.util.*;

public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 计算模板串S在文本串T中出现了多少次 * @param S string字符串 模板串 * @param T string字符串 文本串 * @return int整型 */ public int kmp (String S, String T) { //特殊情况判断 int m=S.length(),n=T.length(); if(m>n||n==0) return 0;

    //初始化计数，获取next数组
    int count=0;
    int[] next=getNext(S);
    
    //遍历主串和模式串
    for(int i=0,j=0;i<n;i++){
        //只要不相等，回退到next数组记录的下一位
       while(j > 0 && S.charAt(j) != T.charAt(i)){
           j = next[j - 1];
       }
        if(S.charAt(j) == T.charAt(i)) j ++;
        if(j == m){
            count ++;
            j = next[j-1];
        }
    }
    return count;
}

//确定next数组
private int[] getNext(String S){
   int len = S.length();
    int[] next = new int[len];
    for(int i = 1,j = 0;i < len;i ++){
        if(j > 0 && S.charAt(j) != S.charAt(i)){
            j = next[j -1];
        }
        if(S.charAt(i) == S.charAt(j)) j++;
        next[i] = j;
    }
    return next;
}

}