KMP算法

public class KMP {
    public static void main(String[] args) {
        System.out.print(kmp("abcde","cde"));
    }

    public static int kmp(String t ,String p){
        if (t.length() == 0 || p.length() == 0){
            return -1;
        }
        int[] next = new int[p.length()];
        getNext(p,next);
        //扫描主串
        int i = 0;
        //扫描模式串
        int j = 0;
        while (i < t.length() && j < p.length()){
            if (j == -1 || t.charAt(i) == p.charAt(j)){
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        //j的数值等于模式串的长度，说明匹配成功
        if (j == p.length()){
            return i - j;
        }else {
            return -1;
        }
    }

    //由模式串p求出next数组
    public static void getNext(String p,int next[]){
        int j = 0;
        int k= -1;
        next[0] = -1;
        while (j < p.length() -1){
            //k遍历前缀，j遍历后缀
            if (k == -1 || p.charAt(j) == p.charAt(k)){
                j++;
                k++;
                next[j] = k;
            }else {
                k = next[k];
            }
        }
    }
}