KMP algorithm

很久以前看到的KMP算法，重新回顾了一下。主要就是如何寻找next数组。
对于类似字符串A,aaaaaaab,与字符串B，aaab。寻找A中包含字符串B的位置。
如果使用暴力搜索，每次失配都需要从A的下一位开始，但其实并不用。对于这个例子来说，
前面的两位是不需要再次判断的，因为有公共的前后缀，因此构建一个next数组如下。
B： a a a b
index: 0 1 2 3
next: 0 1 2 0

假设我们已经知道了aa这个字符串的值为1，那么如果新加入另一个字母a，则判断index为1的值和该值是否相同。
相同，则在之前的前缀表长度加一，如果不同，则找到前一个字符的前缀表，进行如上的判断。

最后进行匹配的时候，则在失配时候可以直接跳过已经匹配过的前缀。

public static int[] next(char[] target) {
    int[] res = new int[target.length];
    res[0] = 0;
    int i = 1;
    int len = 0;
    while (i < target.length) {
        if (target[i] == target[len]) {
            len++;
            res[i] = len;
            i++;
        } else {
            if (len == 0) {
                res[i] = 0;
                i++;
            } else {
                //找到前一个字母的前缀表
                len = res[len - 1];
            }
        }
    }
    for (int j = res.length - 1; j >= 1; j--) {
        res[j] = res[j - 1];
    }
    res[0] = -1;
    return res;
}

public static void main(String[] args) {
    char[] arr = "ABABCABAA".toCharArray();
    char[] res = "ABABABCABAABABABA".toCharArray();
    int[] next =  next(arr);
    int i = 0;
    int j = 0;
    while( i < res.length){
        if( j == arr.length - 1 && arr[j] == res[i]){
            //匹配到了
            System.out.println("find at index "+ (i - j));
            //继续匹配
            j = next[j];
        }
        if(res[i] == arr[j]){
            i++;
            j++;
        }
        else{
            j = next[j];
            if(j == - 1){
                j++;
                i++;
            }
        }
    }
}