package com.zou.Algorithm.kmp;

import java.util.Arrays;

public class KmpAlgorithm {
    public static void main(String[] args) {
        String str1="BBC ABCDAB ABCDABCDABDE";
        String str2="ABCDABD";
        int[] next=kmpNext("ABCDABD");
        System.out.println("next="+ Arrays.toString(next));
        int index=kmpSearch(str1,str2,next);
        System.out.println("index="+index);
    }
    //搜索算法
    public static int kmpSearch(String str1,String str2,int[] next){//next匹配表
        for (int i = 0,j=0; i < str1.length(); i++) {
            while(j>0&&str1.charAt(i)!=str2.charAt(j)){
                j=next[j-1];//核心
            }
            if (str1.charAt(i)==str2.charAt(j)){
                j++;
            }
            if (j==str2.length()){
                return i-j+1;
            }
        }
        return -1;
    }
    //获取字符串的部分匹配值表
    public static int[]kmpNext(String dest){
        //创建一个数组保存next匹配值
        int[] next = new int[dest.length()];
        next[0]=0;//如果字符串长度是1，部分匹配值就是0
        for (int i = 1,j=0; i < dest.length(); i++) {//
            //dest.charAt(i)!=dest.charAt(j)不等从next[]从新获取
            //直到成立dest.charAt(i)==dest.charAt(j)退出
            while(j>0&&dest.charAt(i)!=dest.charAt(j)){
                j=next[j-1];//核心
            }
            if (dest.charAt(i)==dest.charAt(j)){
                j++;
            }
            next[i]=j;
        }
        return next;
    }

}