另类字符匹配方式

存在一个字符串 ababababc 问是否存在字符串 ababc
普通方式：

    public static int search(String pat,String txt){
        int len = txt.length();
        int pLen = pat.length();
        for(int i=0;i<len-pLen;i++){
            int j = 0;
            for( j=0;j<pLen;j++){
                if(pat.charAt(j) != txt.charAt(i+j)){
                    break;
                }
            }
            if(j == pLen) return i;
        }
        return -1;

    }
    
    public static void main(String[] args) {
        String pat = "ababc";
        String txt = "ababababc";
        System.out.println(search(pat, txt));
    }

第二种方式：

 public class KMP2 {
   private int[][] dp;
   private String pat;

   // 构建dp数组
   public KMP2(String pat){
       int m = pat.length();
       this.pat = pat;
       this.dp = new int[m][256];
       dp[0][pat.charAt(0)] = 1;
       int x = 0;
       for(int i=1;i<m;i++){
           for(int j=0;j<256;j++){
               if(pat.charAt(i) == j){
                   dp[i][j] = i+1;
               }else{
                   dp[i][j] = dp[x][j];
               }
           }
           x = dp[x][pat.charAt(i)];
       }
   }

   public int serach(String txt){
       int len = txt.length();
       int j =0;
       for(int i=0;i<len;i++){
           j = dp[j][txt.charAt(i)];
           if(j == pat.length()) return i-pat.length()+1;
       }
       return -1;
   }

    public static void main(String[] args) {
        KMP2 kmp2 = new KMP2("ababc");
        System.out.println(kmp2.serach("ababababc1111"));
    }

}