import java.util.Arrays;
/**
 * ClassName: KmpTest
 * Description:
 * date: 2021/2/19 10:15
 *
 * @author ZhuQiPeng
 * @since JDK 1.8
 */
public class KmpTest {
    public static void main(String[] args) {
        String desStr = "BABABACABABCABAABD";
        String subStr = "ABABCABAAB";
        int[] next = getNext(subStr);
        System.out.println(Arrays.toString(next));
        int index = kmp(desStr,subStr);
        System.out.println(index);
    }
    public static int[] getNext(String subStr){
        int[] next = new int[subStr.length()];
        next[0] = -1;
        int len = -1, y = 0;
        while (y < subStr.length() - 1){
            if(len == -1 || subStr.charAt(len) == subStr.charAt(y)) {
                y++;
                len++;
                next[y] = len;
            }else{
                len = next[len];
            }
        }
        return next;
    }
    public static int kmp(String desStr, String subStr){
        int x = 0,y = 0;
        int[] next = getNext(subStr);
        while (x < desStr.length() && y < subStr.length()){
            if(y == -1 || subStr.charAt(y) == desStr.charAt(x)){
                x++;
                y++;
            }else{
                y = next[y];
            }
        }
        if (y == subStr.length()){
            return x-y;
        }else{
            return -1;
        }
    }
}