题解 | #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 sl=S.length();
        int tl=T.length();
        int count=0;
        int[] next=getNext(S);
        int j=0;
        for(int i=0;i<tl;i++)
        {
            while(j>0&&S.charAt(j)!=T.charAt(i))
            {
                j=next[j-1];
            }
            if(S.charAt(j)==T.charAt(i))
            {
                j++;
            }
            if(j==sl)
            {
                count++;
                j=next[j-1];//会退回去继续判断
            }

        }
        return  count;
    }
    public int[] getNext(String S) {
        int l = S.length();
        // 获得next数组
        int[] next = new int[l];
        next[0] = 0; //没有公共前缀
        int j = 0;
        // AABAS
        // 01
        for (int i = 1; i < l; i++) {
            while (j > 0 && S.charAt(j) != S.charAt(i)) {
                j = next[j - 1]; //会退一步判断
                // ：next[j - 1] 表示在 S[0...j-1] 这个子字符串中，最长的相同前缀和后缀的长度。如果 S[j] 和当前要比较的字符不匹配，这意味着 S[j] 不能作为前缀的一部分，因此需要找到一个更短的前缀，使得 S[0...next[j-1]] 和 S[i...] 能够匹配。
            }
            if (S.charAt(j) == S.charAt(i)) {
                j++;
            }
            next[i] = j; //验证到了这一步了。

        }
        return next;
    }
}

next和kmp的for循环思路一样，只是多了一个子字符串次数的判断；jnext[j-1]

注意while判断在前头，他决定j的退回多少到哪里。