题解 | #kmp算法#

建议背住，匹配的过程和求next的过程很相似。

public class Solution {
    public int kmp (String S, String T) {
        // write code here
        int count = 0;
        int[] next = new int[S.length()];
        getNext(S, next);
        for (int i = 0, j = 0; i < T.length(); ++i) {
            if (j > 0 && S.charAt(j) != T.charAt(i)) {
                j = next[j - 1];
            }
            if (S.charAt(j) == T.charAt(i)) {
                j++;
            }
            if (j == S.length()) {
                count++;
                j = next[j-1];
            }
        }
        return count;
    }
    public void getNext(String s, int[] next) {
        int i = 1, j = 0;
        for (; i < s.length(); ++i) {
            if (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = next[j - 1];
            }
            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
    }
}