题解 | #kmp算法#

题解参考链接:
https://blog.csdn.net/qq1137623160/article/details/102589408
日 看不懂 还是死记硬背吧

import java.util.*;


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

        int[] next = buidKmpNextArray(S);
        int count = kmpSearch(S, T, next);
        return count;
    }

    public int kmpSearch (String S, String T, int[] next) {

        int count = 0;

        for (int i = 0,j = 0; i < T.length(); i++) {

            while (j > 0 && T.charAt(i) != S.charAt(j)) {
                j = next[j - 1];
            }

            if (T.charAt(i) == S.charAt(j)) {
                j++;
            }

            if (j == S.length()) {
                j = next[j - 1];
                count++;
            }
        }

        return count;
    }

    //获取到一个字符串(子串) 的部分匹配值表
    public int[] buidKmpNextArray (String patternStr) {

        //创建一个 next 数组保存部分匹配值
        int[] next = new int[patternStr.length()];

        //如果字符串是长度为 1 部分匹配值就是 0
        next[0] = 0;

        for (int i = 1,j = 0; i < patternStr.length(); i++) {

            //当 dest.charAt(i) != dest.charAt(j) ，我们需要从 next[j-1]获取新的 j
            //直到我们发现 有 dest.charAt(i) == dest.charAt(j)成立才退出
            //这时 kmp 算法的核心点
            while (j > 0 && patternStr.charAt(i) != patternStr.charAt(j)) {
                j = next[j - 1];
            }

            //当 dest.charAt(i) == dest.charAt(j) 满足时，部分匹配值就是+1
            if (patternStr.charAt(i) == patternStr.charAt(j)) {
                j++;
            }

            next[i] = j;
        }

        return next;
    }
}