题解 | #kmp算法|KMP变体#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * <p>
     * 计算模板串S在文本串T中出现了多少次
     *
     * @param T string字符串 模板串
     * @param S string字符串 文本串
     * @return int整型
     */
    public int kmp(String T, String S) {
        char[] sArr = S.toCharArray();
        char[] tArr = T.toCharArray();
        int s = 0;
        int t = 0;
        int count = 0;
        int[] next = getNext(T);
        System.out.println(Arrays.toString(next));
        while (s < sArr.length) {
            if (sArr[s] == tArr[t]) {
                s++;
                t++;
            } else if (t == 0) {
                s++;
            } else {
                t = next[t];
            }
            // 设虚拟串为T+' ' ,问题在S中匹配T转换为在S中匹配T+' '
            // 当t == tArr.length时认为T+' '没有匹配到，但此时T已经匹配到，count++,
            // 而T+' '则根据next数组继续回溯匹配
            if (t == tArr.length) {
                count++;
                t = next[t];
            }
        }
        return count;
    }

    private int[] getNext(String T) {
        // 设len为T的长度，在原生KMP的next数组上加一个位置next[len],用于记录T[0]~T[len-1]的最长公共前缀长度
        T = T + 'z';
        char[] tArr = T.toCharArray();
        int[] next = new int[tArr.length];
        int i = 1;
        int k = 0;
        next[0] = -1;
        while (i < tArr.length - 1) {
            if (tArr[k] == tArr[i]) {
                ++i;
                ++k;
                if (tArr[i] != tArr[k]) {
                    next[i] = k;
                } else {
                    next[i] = next[k];
                }
            } else if (k == 0) {
                next[++i] = 0;
            } else {
                k = next[k];
            }
        }
        return next;
    }
}