package 字符串;

public class KMP {
    public static int[] getNextarr(char[] str2) {
        if(str2.length < 2) {
            return new int[]{ -1 };
        }
        int[] next = new int[str2.length];
        next[0] = -1;
        next[1] = 0;
        int cn = 0; // cn指的是跳到的位置也就是字符串中i-1位置字符最大前綴+1的位置
        int i= 2; // str2中各個字符的指針 
        while(i < str2.length) {
            if(str2[i - 1] == str2[cn]) {
                next[i++] = ++cn;
            }else if(cn > 0){
                cn = next[cn];     // 往后跳一個
            }else {
                next[i++] = 0;
            }
        }
        return next;
    }
    public static int getIndexof(String s1, String s2) {
        if(s2 == null) {
            return -1;
        }
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        int[] next = getNextarr(str2);
        int i = 0;
        int j = 0;
        while(i < str1.length && j < str2.length) {
            if(str1[i] == str2[j]) {
                i++;
                j++;
            }else if(next[j] == -1) {
                i++;
            }else {
                j = next[j];
            }
        }
        return j == str2.length ? i - j : -1;   // 如果j!=str2.length就說明str1中不存在str2這個子序列
    }
    public static void main(String[] args) {
        String s1 = "abcabaaaa";
        String s2 = "a";
        int res = getIndexof(s1, s2);
        // int res1 = s1.indexOf(s2);
        System.out.println(res);
    }
}