题解 | #kmp算法#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算模板串S在文本串T中出现了多少次
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    public int kmp (String S, String T) {
        if (S == null || T == null || "".equals(S) || "".equals(T) 
            || S.length() > T.length()) {
            return 0;
        }
        int result = 0;
        int[] next = getNext(S);
        int index = 0;
        for (int i = 0; i < T.length(); i++) {
            if (S.charAt(index) == T.charAt(i)) {
                if (index == S.length() - 1) {
                    result++;
                    index = next[index];
                } else {
                    index++;
                }
            } else {
                if (index > 0) {
                    index = next[index - 1];
                    i--;
                }
            }
        }
        return result;
    }
    public static int[] getNext(String S) {
        // next[i]代表i位置最长有长度为next[i]的前缀与当前后缀匹配
        int[] next = new int[S.length()];
        next[0] = 0;
        if (S.length() > 1 && S.charAt(0) == S.charAt(1)) {
            next[1] = 1;
        }
        // 用于遍历next数组，为每个位置赋值
        int increaseIndex = 2;
        // 用于回溯查找
        int tempIndex = increaseIndex;
        int tempValue;
        while (increaseIndex < S.length() && tempIndex < S.length()) {
            tempValue = next[tempIndex - 1];
            tempIndex = tempValue;
            if (S.charAt(tempIndex) == S.charAt(increaseIndex)) {
                next[increaseIndex] = tempValue + 1;
                increaseIndex++;
                tempIndex = increaseIndex;
            } else {
                if (tempIndex == 0) {
                    increaseIndex++;
                    tempIndex = increaseIndex;
                }
            }
        }
        return next;
    }
}