import java.util.Scanner;

public class KMP算法 {

    //计算目标串的前缀与后缀匹配关系
    static void cal_next(String  ptr1,int [] next){
        char[] ptr = ptr1.toCharArray();//把字符串str1变成字符数组str
        int plen = ptr1.length();
        next[0] = -1;//-1表示不存在相同的最大前缀和最大后缀
        int k = -1;//k初始化为-1，为什么是-1而不是0？
        // 因为k其实要被用作kmp算法中的下标
        //str[] =    a b c a b d a b c a b c      在i=5时不匹配
        //ptr[] =    a b c a b c            在k=4时不匹配，因为匹配规则是ptr[k+1] == str[i]所以k=4
        //这时目标串需要向后移动，移动3位，但是由于前缀abc与后缀abc相同,且后缀与主串已经比较过，
        //所以移动三位后目标串前缀中的a b已经相当于已经与主串中的ab比较过，可以不用再次进行比较，这样就用到了next[]中k的值即下标
        //k可以直接取到next[4]=1,k=1,进行ptr[k+1]==str[i]的最新比较，提高效率
        for (int p = 1;p <= plen - 1;p ++){//对目标串自己进行比较
            while(k > -1 && ptr[k+1] != ptr[p]){
                k = next[k];//向前回溯
            }
            if(ptr[k+1] == ptr[p]){//相同,k++
                k = k+1;
            }
            next[p] = k;//这个是把算的k的值（就是相同的最大前缀和最大后缀长）赋给next[p]
        }

    }
    //KMP
    static int KMP(String str1,String  ptr1){
        char[] str = str1.toCharArray();//把字符串str1变成字符数组str
        char[] ptr = ptr1.toCharArray();//把字符串ptr1变成字符数组ptr
        int slen = str1.length();
        int plen = ptr1.length();
        //创建一个next数组，数组长度为目标串长度plen
        int [] next = new int [plen];
        //计算next数组
        cal_next(ptr1,next);
        int k = -1;//k用来标识目标串下标
        for(int i = 0;i < str1.length();i ++){
            //k>-1表示有部分匹配，ptr[k+1] != str[i]表示在i下标位置不匹配
            while(k > -1 && ptr[k+1] != str[i]){
                k = next[k];//k赋值为next[k],目的是让k可以不用重复比较前缀与后缀相偶同的长度的字符
            }
            if(ptr[k+1] == str[i]){//匹配则向后移动
                k++;
            }
            if(k == plen-1){//k移动到ptr的最末端
                return i-plen+1;
            }
        }
        return -1;
    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入主串：");
        String str1 = scanner.next();
        System.out.println("请输入字串:");
        String ptr1 = scanner.next();
//        String str1 = "abcabdabcabc";
//        String ptr1 = "abcabc";
        System.out.println("主串:"+str1);
        System.out.println("子串:"+ptr1);
        int a = KMP(str1,ptr1);
        if(a == -1){
            System.out.println("不匹配");
        }else{
            System.out.println("从第"+a+"个位置后匹配");
        }
    }
}