题解 | #java KMP算法#

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
        char[] s = S.toCharArray();
        char[] t = T.toCharArray();
        int[] next = new int[s.length];
        int res = 0;

        initNext(next, s); // 生成next数组

        for (int i = 0, j = 0; i < t.length; i++) {
            if (j > 0 && t[i] != s[j]) {
                j = next[j - 1];
            }
            if (t[i] == s[j]) {
                j++;
            }
            if (j == s.length) {
                res++;
                j = next[j - 1];
            }
        }

        return res;
    }

    private void initNext (int[] next, char[] s) {

        for (int i = 1, j = 0; i < s.length; i++) {
            while (j > 1 && s[i] != s[j]) {
                j = next[j - 1];
            }
            if (s[i] == s[j]) {
                j++;
            }
            next[i] = j;
        }
    }
}