字符串中的KMP算法及其改进

public class Main {
    public static void main(String[] args) {
        String s = "abcdsaegsdkjflakji"; // 原串
        String p = "gsdk1"; // 模式串
        boolean res = false;
        for(int i=0;i<=s.length()-p.length();i++){
            int j = 0;
            while(j<p.length()){
                if(p.charAt(j)==s.charAt(i+j)){
                    j++;
                }else{
                    break;
                }
            }
            if(j==p.length()){
                res = true;
                break;
            }
        }
        if(res){
            System.out.println(s + " 包含了 " +p);
        }else{
            System.out.println(s + " 不包含 " +p);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        String p = "ABABABB";
        String s = "ABAAABABABBAABBA";
        int[] next = kmp(p);
        System.out.printf("next数组=");
        for(int k : next){
            System.out.printf("%d \t",k);
        }
        System.out.println();
        int i = 0;
        int j = 0;
        while(j<p.length() && i<s.length()){
            if(p.charAt(j) == s.charAt(i)){
                i++;
                j++;
            }else{
                j = next[j]-1;
                if(j<0){
                    j = 0;
                    i++;
                }
            }
        }
        //判断匹配是否成功
        boolean res = j==p.length();
        System.out.println("主串s = "+s);
        System.out.println("子串p = "+p);
        if(res){
            System.out.println("匹配成功");
        }else{
            System.out.println("匹配失败");
        }
    }
    /**
     * next数组是第几个元素，因此n从1开始
     */
    public static int[] kmp(String p){
        int[] next = new int[p.length()];
        next[0]=0;
        /**
         * 当前不匹配元素发生在i位置
         */
        for(int i=1;i<p.length();i++){
            /**
             * 子串向右移动的距离为step
             */
           int step = 1;
           while(step<=i){
               /**
                * 子串的新下标
                */
               int idxSon = 0;
               /**
                * 主串的新下标
                */
               int idxPar = step;
               while(idxPar<i){
                   if(p.charAt(idxPar) == p.charAt(idxSon)){
                       idxPar++;
                       idxSon++;
                   }else{
                       break;
                   }
               }
               /**
                * 说明之前匹配成功了
                */
               if(idxPar == i){
                   next[i] = i-step+1;
                   break;
               }
               step++;
           }
        }
        return next;
    }
}