KMP.java

/**
 * 
 */

public class KMP {

    /**
     * https://www.jianshu.com/p/e2bd1ee482c3
     */
    public static int find(String txt, String pat, int[] next) {
        int M = txt.length();
        int N = pat.length();
        int i = 0;
        int j = 0;
        while (i < M && j < N) {
            if (j == -1 || txt.charAt(i) == pat.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
            if (j == N) return i - j;
        }
        return -1;
    }

    public static int[] getNext(String pat) {
        int N = pat.length();
        int[] next = new int[N];
        next[0] = -1;
        int k = -1;
        int j = 0;
        while (j < N - 1) {
            if (k == -1 || pat.charAt(j) == pat.charAt(k)) {
                k++;
                j++;
                next[j] = k;
            } else {
                k = next[k];
            } 
        }
        return next;
    }


    public static void main(String[] args) {
        String txt = "BBC ABCDAB CDABABCDABCDABDE";
        String pat = "ABCDABD";
        int[] next = getNext(pat);
        System.out.println(find(txt, pat, next));
    }

}