题解 | #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 lenS = S.length();
        int lenT = T.length();
        int[] next = new int[lenS];
        for(int i = 1,j = 0;i < lenS;i++) {
            while(j > 0 && S.charAt(i) != S.charAt(j)) {
                j = next[j-1];
            }
            if(S.charAt(i) == S.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        int res = 0;
        for(int i = 0,j = 0;i < lenT;i++) {
            while(j > 0 && T.charAt(i) != S.charAt(j)) {
                j = next[j-1];
            }
            if(T.charAt(i) == S.charAt(j)) {
                j++;
            }
            if(j == lenS) {
                res++;
                j = next[j-1];
            }
        }
        return res;
    }
}