java实现kmp算法

kmp

next[j] = k，表示当T[i] != P[j]时，j指针的下一个位置

public class KMP {

    public int kmp(char[] s, char[] t) {
        int[] next = new int[t.length];
        int i = 0, j = 0;
        getNext(next, t);
        while (i < s.length && j < t.length) {
            if (j == -1 || s[i] == t[j]) {
                i++;
                j++;
            } else {
                // j回退
                j = next[j];
            }
        }
        if (j >= t.length) {
            return i - t.length;
        } else {
            return -1;
        }
    }

    public void getNext(int[] next, char[] t) {
        int j = 0, k = -1;
        next[0] = -1;
        while (j < t.length - 1) {
            if (k == -1 || t[j] == t[k]) {
                j++;
                k++;
                next[j] = k;
            } else {
                k = next[k];
            }
        }
    }

    // 改进next数组
    public void getNext2(int[] next, char[] t) {
        int j = 0, k = -1;
        next[0] = -1;
        while (j < t.length - 1) {
            if (k == -1 || t[j] == t[k]) {
                j++;
                k++;
                //当两个字符相同时，就跳过
                if(t[j]==t[k]) {
                    next[j] = next[k];
                }
                else {
                    next[j] = k;
                }
            } else {
                k = next[k];
            }
        }
    }

}