public class StringMatching {
    public static void main(String[] args) {
        //暴力匹配算法
        String str1 = "硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好";
        String str2 = "尚硅谷你尚硅你";
        int match = violenceMatch(str1, str2);
       // System.out.println(match);

        String s1= "BBC ABCDAB ABCDABCDABDE";
        String s2 = "ABCDABD";
        String s3 = "ABC";
        int[] next = kmpNext("ABCDABD");//[0,1]
        int res = kMP(s1, s2, next);
        System.out.println(Arrays.toString(next));
        System.out.println(res);

    }


    /*暴力匹配算法*/
    public  static  int violenceMatch(String str1,String str2){
      char[] s1 = str1.toCharArray();
      char[] s2 = str2.toCharArray();
      int i=0;//索引指向s1
      int j = 0;//索引指向s2
        while (i<s1.length&&j<s2.length){//匹配不越界
            if (s1[i] ==s2[j]){//匹配成功
               i++;
               j++;
            }else {//不成功
                i = i -(j-1);
                j=0;
            }
        }
        //判断是否匹配成功
        if (j==s2.length){
            return  i-j;
        }else {
            return -1;
        }
    }

   /*获取到一个字符串的部分匹配值*/
    public static  int[] kmpNext(String dest){
        /*保存部分匹配值*/
        int[] next = new int[dest.length()];
        next[0] = 0;//如果字符串长度为1；部分匹配值是0；
        for (int i = 1 ,j=0; i <dest.length() ; i++) {
            //当不相等时需要从j-1获取新的j
            /*直到发现dest.charAt(i) == dest.charAt(j)退出*/
               while (j>0 &dest.charAt(i) != dest.charAt(j)){
                   j=next[j-1];//kmp算法的基础
               }
        if (dest.charAt(i) == dest.charAt(j)){
            j++;
        }
        next[i] =j;
        }
        return next;
    }

    /*KMP算法查找字符最早出现的位置*/
    public  static  int kMP(String str1,String str2,int[] next){
        for (int i = 0 ,j=0; i <str1.length() ; i++) {

            /*需要考虑str1.charAt(i) ！=str2.charAt(j)时*/
            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;
    }

}