1 暴力破解

 

java实现如下：

1 public class Naive { 2  3     /** 4      * 暴力破解 5      * 6      * @param pat 7      * @param txt 8      * @return 9      */10     private static int search(String pat, String txt) {11         int m = pat.length();12         int n = txt.length();13         for (int i = 0; i <= n - m; i++) {14             int j;15             for (j = 0; j < m; j++) {16                 if (txt.charAt(i + j) != pat.charAt(j)) {17                     break;18                 }19             }20             if (j == m) {21                 return i;22             }23         }24         return n;25     }26 27     public static void main(String[] args) {28         int pos = search("abcabd", "abcabcabdabba");29         System.out.println(pos);30     }31 32 }

 最坏的情况是：

常见的是二进制情况下的匹配：

 

 

 

2 KMP算法

如果用暴力方法解决的话就会有大量的回溯，每次只移动一位，若是不匹配，移动到下一位接着判断，浪费了大量的时间：

 

所以，kmp方法算法就利用之前判断过信息，通过一个next数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过next数组找到，前面匹配过的位置，省去了大量的计算时间。

1 public class KMP { 2     public static int KMP(String pat, String txt) { 3         char[] t = pat.toCharArray(); 4         char[] p = txt.toCharArray(); 5  6         int i = 0; // 主串的位置 7         int j = 0; // 模式串的位置 8         int[] next = getNext(txt); 9 10         while (i < t.length && j < p.length) {11             if (j == -1 || t[i] == p[j]) { // 当j为-1时，要移动的是i，当然j也要归012                 i++;13                 j++;14             } else {15                 // i不需要回溯了16                 // i = i - j + 1;17                 j = next[j]; // j回到指定位置18             }19         }20 21         if (j == p.length) {22             return i - j;23         } else {24             return -1;25         }26     }27 28     public static int[] getNext(String ps) {29         char[] p = ps.toCharArray();30         int[] next = new int[p.length];31         next[0] = -1;32 33         int j = 0;34         int k = -1;35         while (j < p.length - 1) {36             if (k == -1 || p[j] == p[k]) {37                 next[++j] = ++k;38             } else {39                 k = next[k];40             }41         }42         return next;43     }44 45     public static void main(String[] args) {46         String pat = "abcabd";47         String txt = "abcabcabdabba";48         int pos = KMP(pat, txt);49         System.out.println(pos);50     }51 52 }

 

kmp算法的核心时间复杂度就是O（m+n）