BF算法
BF算法，简称暴力破解 Bruce Force ，又称朴素模式的匹配算法。
可以看出BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，
若相等，则继续比较S的第二个字符和T的第二个字符；
若不相等，则比较S的第二个字符和T的第一个字符，依次比较，直到得出最后的匹配结果。
这种算法的比较很暴力，由于产生了多次的回溯，在效率上存在很大的缺陷。
时间复杂度O（m*n）
代码：
1 package bf; 2
3 public class Test { 4 public static void main(String[] args) { 5 String bf = "IloveChinveChia"; 6 String pattern = "veChi"; 7 int m = bf.length(); // i
8 int n = pattern.length(); // j
9 int i = 0, j = 0; 10 while (i < m) { 11 if (bf.charAt(i) == pattern.charAt(j)) { // 一一匹配时
12 i++; 13 j++; 14 } else { 15 i = i - j + 1; 16 j = 0; 17 } 18 if (i == m) 19 break; 20 if (bf.charAt(i) == pattern.charAt(j) && j == n - 1) { 21 System.out.println(i - j); 22 if (i < m) { 23 j = 0; 24 } else { 25 break; 26 } 27 } 28 } 29 } 30 }
KMP算法
代码：
1 package kmp; 2
3 public class Test { 4
5 public static void main(String[] args) { 6 String text = "ABABABCABAASFAWAIFAS"; 7 String pattern = "ABABCABAA"; 8 kmp_search(text, pattern); 9 } 10 //计算公共前后缀，形成前缀表
11 static void prefix_table(String pattern, int prefix[], int n) { 12 prefix[0] = 0; 13 int len = 0; 14 int i = 1; 15 while (i < n) { 16 if (pattern.charAt(i) == pattern.charAt(len)) { 17 len++; 18 prefix[i] = len; 19 i++; 20 } else { 21 if (len > 0) { 22 len = prefix[len - 1]; 23 } else { 24 prefix[i] = len; 25 i++; 26 } 27 } 28 } 29 } 30 //移位 ---》 next数组
31 static void move_prefix_table(int prefix[], int n) { 32 int i; 33 for (i = n - 1; i > 0; i--) { 34 prefix[i] = prefix[i - 1]; 35 } 36 prefix[0] = 0; 37 } 38 // kmp算法 依据 next数组来匹配字符串
39 static void kmp_search(String text, String pattern) { 40 int n = pattern.length(); 41 int m = text.length(); 42 int prefix[] = new int[n]; 43 prefix_table(pattern, prefix, n); 44 move_prefix_table(prefix, n); 45 // ----------做好准备工作(计算出next数组)------------- 46 // text[i] len(text) = m 47 // patten[j] len(partten) = n
48 int i = 0, j = 0; 49 while (i < m) { 50 if (j == n - 1 && text.charAt(i) == pattern.charAt(j)) { 51 System.out.println("Found pattern at:" + (i - j)); 52 j = prefix[j]; 53 } 54 if (text.charAt(i) == pattern.charAt(j)) { 55 i++; 56 j++; 57 } else { 58 j = prefix[j]; 59 if (j == -1) { 60 i++; 61 j++; 62 } 63 } 64 } 65 } 66 }
参考资料：
https://blog.csdn.net/x__1998/article/details/79951598
https://www.bilibili.com/video/av16828557?t=1484
https://www.cnblogs.com/yjiyjige/p/3263858.html