题解 | #kmp算法#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算模板串S在文本串T中出现了多少次
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    public int kmp (String S, String T) {
        // write code here

        int S_len = S.length(), T_len = T.length();
        char[] chs = S.toCharArray();
        char[] cht = T.toCharArray();
        int val=0;
        int[] F = new int[S_len];
        int i=1,j=0;
        F[0]=0;
        while(i<S_len ){   //对S字符串进行预处理，建立内部滑动关系。
            if(chs[i]==chs[j]){
                F[i] = j+1;
                i++;
                j++;
            }
            else if(j>0)
                j = F[j-1];
            else{
                F[i] = 0;
                i++;
            }
        }
        i=0;
        j=0;
        while(i<T_len){
            if(chs[j]==cht[i]){
                if(j==(S_len-1)){
                    val++;
                    j= F[j]; //回到数组最大可滑动幅度
                    i++;
                }
                else{i++;j++;}
            }
            else if(j>0)
                j = F[j-1]; //回到前一个类似的关联点
            else
                i++;
        }
        return val;
    }
}