字符串的匹配算法有：
1、单模式串匹配算法（BF算法，RK算法，BM算法，KMP算法）
2、多模式串匹配算法有（Trie树，AC自动机）
BF（Brute Force）算法
BF算法就是拿模式串m，从主串n的第0位开始匹配，如果匹配不成功，则后移一位继续匹配。
是比较简单的一种字符串匹配算法，在处理简单的数据时候就可以用这种算法，完全匹配，速度很慢，时间复杂度最坏情况O(M*N)。
1 | public static int bf(String str,String sub){ |
RK（Rabin-Karp）算法
RK算法：数字的匹配比字符串快速，就把主串中的这n-m+1的子串分别求哈希值，然后在分别跟模式串的哈希值进行比较。如果哈希值不一样那肯定不匹配，如果哈希值一样，因为哈希算法存在哈希冲突，这时候在拿模式串跟该子串对比一下就好了。
虽然模式串跟子串的对比速度提高了，但是我们事先需要遍历主串，逐个求子串的哈希值，这部分也挺耗时的，所以需要设计比较高效的哈希算法尽量的减少哈希冲突的产生。
BM（Boyer-Moore）算法
上面两种字符串匹配算法都有缺点，BF算法在极端情况下效率会很低，RK算法需要有一个很好的哈希算法，而设计一个好的哈希算法并不简单，有没有尽可能的高效，极端情况下效率退化也不大的算法呢，下面看看BM算法。
BM算法是一种非常高效的算法，各种记事本的查找功能一般都是采用的这种算法。该算法从模式串的尾部开始匹配，且拥有在最坏情况下 O(N) 的时间复杂度。在实践中，比 KMP 算法的实际效能高。
BM 算法定义了两个规则：
- 坏字符规则：当文本串中的某个字符跟模式串的某个字符不匹配时，我们称文本串中的这个失配字符为坏字符，此时模式串需要向右移动，移动的位数 = 坏字符在模式串中的位置 坏字符在模式串中最右出现的位置。此外，如果”坏字符”不包含在模式串之中，则最右出现位置为 -1。
- 好后缀规则：当字符失配时，后移位数 = 好后缀在模式串中的位置 - 好后缀在模式串上一次出现的位置，且如果好后缀在模式串中没有再次出现，则为 -1。
通过坏字符算法与好后缀算法分别获取位移值，取两者中的最大值进行位移操作。
案例可参考：http://wiki.jikexueyuan.com/project/kmp-algorithm/bm.html
BM算法完整代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67// a,b 表示主串和模式串；n，m 表示主串和模式串的长度。
public int bm(char[] a, int n, char[] b, int m) {
int[] bc = new int[SIZE]; // 记录模式串中每个字符最后出现的位置
generateBC(b, m, bc); // 构建坏字符哈希表
int[] suffix = new int[m];
boolean[] prefix = new boolean[m];
generateGS(b, m, suffix, prefix);
int i = 0; // j 表示主串与模式串匹配的第一个字符
while (i <= n - m) {
int j;
for (j = m - 1; j >= 0; --j) { // 模式串从后往前匹配
if (a[i+j] != b[j]) break; // 坏字符对应模式串中的下标是 j
}
if (j < 0) {
return i; // 匹配成功，返回主串与模式串第一个匹配的字符的位置
}
int x = j - bc[(int)a[i+j]];
int y = 0;
if (j < m-1) { // 如果有好后缀的话
y = moveByGS(j, m, suffix, prefix);
}
i = i + Math.max(x, y);
}
return -1;
}
// j 表示坏字符对应的模式串中的字符下标 ; m 表示模式串长度
private int moveByGS(int j, int m, int[] suffix, boolean[] prefix) {
int k = m - 1 - j; // 好后缀长度
if (suffix[k] != -1) return j - suffix[k] +1;
for (int r = j+2; r <= m-1; ++r) {
if (prefix[m-r] == true) {
return r;
}
}
return m;
}
private void generateBC(char[] b, int m, int[] bc) {
for (int i = 0; i < m; ++i) {
bc[i] = -1;
}
for (int i = 0; i < m; ++i) {
int ascii = (int) b[i];
bc[ascii] = i; // 如果ascii相同只需要存储 bc[ascii] = 最后一个
}
}
private void generateGS(char[] b, int m, int[] suffix, boolean[] prefix) {
for (int i = 0; i < m; ++i) { //初始化
suffix[i] = -1;
prefix[i] = false;
}
for (int i = 0; i < m - 1; ++i) { // b[0,i]
int j = i;
int k = 0;
while (j >= 0 && b[j] == b[m - 1 - k]) {
--j;
++k;
suffix[k] = j + 1;//记录模式串每个可以匹配前缀子串的长度 等于 最大下标值
}
if (j == -1) prefix[k] = true;
}
}
KMP（Knuth Morris Pratt）算法
模式串跟主串左端对齐，先比较第一个字符，如果不一样就，模式串后移，直到第一个字符相等
第一个字符匹配上之后在匹配第二个，直到有不相等的为止，比如下面
主串：cdababaeabac
模式串：ababacd
e和c不匹配，e就可以理解为坏字符，ababa可以理解为好前缀，那移动几位呢？
我们拿好前缀本身，在它的后缀子串中查找最长的那个可以跟好前缀的前缀子串匹配的。
移动位数 = 已匹配的字符数 - 对应的部分匹配值的长度
如何求这个对应的匹配值呢？这个不涉及到主串只需要根据模式串就可以求出来。
比如这里的模式串是 ababacd
a的前缀和后缀都是空，共有元素为0
ab的前缀是[a]后缀是[b]，共有元素为0
aba的前缀是[a,ab]后缀是[ba,a]，共有元素a的长度是1
abab的前缀是[a,ab,aba]后缀是[bab,ab,b],共有元素是[ab]长度为2
ababa的前缀是[a,ab,aba,abab]后缀是[baba,aba,ba,a],最长共有元素是[aba]长度是3
ababac的前缀是[a,ab,aba,abab,ababa]后缀是[babac,abac,bac,ac,c]共有元素为0
ababacd的前缀是[a,ab,aba,abab,ababa,ababac]后缀是[babacd,abacd,bacd,acd,cd,d]共有元素是0
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33// a, b 分别是主串和模式串；n, m 分别是主串和模式串的长度。
public static int kmp(char[] a, int n, char[] b, int m) {
int[] next = getNexts(b, m);
int j = 0;
for (int i = 0; i < n; ++i) {
while (j > 0 && a[i] != b[j]) { // 一直找到 a[i] 和 b[j]
j = next[j - 1] + 1;
}
if (a[i] == b[j]) {
++j;
}
if (j == m) { // 找到匹配模式串的了
return i - m + 1;
}
}
return -1;
}
// b 表示模式串，m 表示模式串的长度
private static int[] getNexts(char[] b, int m) {
int[] next = new int[m];
next[0] = -1;
int k = -1;
for (int i = 1; i < m; ++i) {
while (k != -1 && b[k + 1] != b[i]) {
k = next[k];
}
if (b[k + 1] == b[i]) {
++k;
}
next[i] = k;
}
return next;
}
参考资料
https://blog.csdn.net/mingyunxiaohai/article/details/87563292
