经典字符串匹配
BF暴力匹配算法
暴力匹配，即Brute Force，简称BF算法。BF算法是一种简单朴素的模式匹配算法，常用于在一个主串S内查找一个子串T的出现位置。
算法步骤
假设有主串S与子串P，主串S的长度为N，子串T的长度为M。
- 将S和T左对齐，并比较其第一个元素。
- 若匹配，则继续比较下一个元素，一直到第M个元素。
- 若不匹配则T向右移动一个位置。
- 接着根据步骤3和4进行比较，直到匹配到或者T移动了N-M且仍未匹配到。
代码实现
Python实现
实现1：
1def BFMatch(s, p):
2 if len(s) < len(p):
3 return -1
4 i, j = 0, 0
5 # 匹配阶段
6 while i < len(s) and j < len(p):
7 # 匹配，s和p的指针均向前一步
8 if s[i] == p[j]:
9 i += 1
10 j += 1
11 # 不匹配，i后退到下一个要匹配的位置，j后头到p开头
12 else:
13 i = i - j + 1
14 j = 0
15 if j == len(p):
16 return i - j
17 return -1
18
19if __name__ == "__main__":
20 s = "abcdefghijkl"
21 p = "ijk"
22 result = BFMatch(s, p)
23 if result == -1:
24 print("False")
25 else:
26 print(result)
实现2：
1def BFMatch(s, p):
2 if len(s) < len(p):
3 return -1
4 # 最多移动len(s)-len(p)+1次
5 # 如果s的前len(s)-len(p)+1个与p均没有匹配
6 # 那么直接判断为不匹配，无需比较后len(p)-1个
7 for i in range(len(s)-len(p)+1):
8 index = i # 当前比较的字符
9 for j in range(len(p)):
10 # 相等继续比较下一个
11 if s[index] == p[j]:
12 index += 1
13 # 不相等停止比较
14 else:
15 break
16 # 如果完全相等，返回当前位置
17 if index - i == len(p):
18 return i
19 return -1
20
21if __name__ == "__main__":
22 s = "abcdefghijkl"
23 p = "ijk"
24 result = BFMatch(s, p)
25 if result == -1:
26 print("False")
27 else:
28 print(result)
C实现
1#include <stdio.h>
2
3int BFMatch(char s[], int len_s, char p[], int len_p) {
4 if (len_s < len_p)
5 return -1;
6 int i = 0, j = 0;
7 // 之匹配s的前len_s-len_p+1个
8 // 如果s[len(s)-len(p)] != p[0]
9 // 那么就不用继续匹配
10 // i-j代表s与p对齐的位置
11 while (i-j <= len_s-len_p) {
12 if (s[i] == p[j]) {
13 i++;
14 j++;
15 if (j == len_p)
16 return i - j;
17 continue;
18 }
19 i = i - j + 1;
20 j = 0;
21 }
22 return -1;
23}
24
25int main(void) {
26#define S "abcdefghijkl"
27#define P "ijk"
28 char s[sizeof(S)] = S;
29 char p[sizeof(P)] = P;
30 int result = BFMatch(s, sizeof(S)-1,
31 p, sizeof(P)-1);
32 if (result == -1)
33 printf("False\n");
34 else
35 printf("%d\n", result);
36 return 0;
37}
KMP快速匹配算法
快速模式匹配算法，即Knuth Morris Pratt（简称KMP）算法，是解决字符串匹配问题的经典算法。
KMP算法是在 BF 算法基础上改进得到的算法。BF算法的实现过程是用子串与主串中的字符一一配对，算法执行效率不高。对于主串S和子串P，BF算法如果遇到了不匹配的情况，主串S和子串P的指针都会回退，而且子串会回退到子串首部。KMP算法的实现过程接近人为进行模式匹配的过程。它只需回退子串，并且是根据情况回退，并不一定要回退到子串首部。
算法步骤
假设有主串S与子串P，主串S的长度为N，子串T的长度为M。
- 求字串P的部分匹配表。
- 将S和T左对齐，并比较其第一个元素。
- 若匹配，则继续比较下一个元素，一直到第M个元素。
- 若不匹配，根据部分匹配表回退P的指针。
- 接着根据步骤3和4进行比较，直到匹配到或者T移动了N-M且仍未匹配到。
失配指针求解
让KMP尽量减少回移的关键在于，用一个部分匹配表（也称失配移动表）记录每次需要回退的位置。部分匹配表是一个与原字符串长度相等的整数数组。表中的元素是字符串中相对于元素的前缀集合和后缀集合的交集中的长度最大的字符串的
假设一个长度为n的模式串为$P=a_0a_1…a_{n-1}$，其中$a_i(0\le i<n)$是单个字符， $Next[\ n+1\ ]$为其部分匹配表。
那么对于$a_{i-1}$：
-
前缀集合：
$$ P_1={a_0,a_0a_1,\cdots,a_0…a_{i-1}} $$
-
后缀集合：
$$ P_2={a_{i-1},a_{i-2}a_{i-1},\cdots,a_1…a_{i-1}} $$
-
失配指针：
$$ Next[i] = \begin{cases} -1 & 当\ i=0 时 \ max & { k|0<k<j 且 “p_0\cdots p_{k-1}” = “p_{j-k}\cdots p_{j-1}” } \ 0 & 其他情况 \end{cases} $$
即：
- $Next[0] = -1$；
- $Next[i] = maxLength(P_1 \cap P_2),\ i \neq 0$。
过程代码演示：
1def get_next_process(p, i, j, next_val):
2 print("第", i + 1, "趟：")
3 print(p)
4 if j != -1:
5 for k in range(i - j):
6 print(" ", end="")
7 print(p)
8 for k in range(i):
9 print(" ", end="")
10 print("^")
11 if i == 0:
12 print("初始化")
13 print(next_val)
14
15def get_next(p):
16 """求部分匹配表（失配指针）"""
17 i = 0 # 指向主串的指针
18 j = -1 # 指向模式串的指针，一开始
19 next_val = [-1] * len(p) # 要返回的next数组
20 get_next_process(p, i, j, next_val)
21 # next[0]==-1，只需要求后面的len(p)-1个值即可
22 while i < len(p)-1:
23 # 匹配成功，相同前缀长度增加1
24 if j == -1 or p[i] == p[j]:
25 i += 1
26 j += 1
27 next_val[i] = j
28 get_next_process(p, i, j, next_val)
29 # 匹配不成功则在前面的子串中继续搜索，直至找不到
30 else:
31 j = next_val[j]
32 return next_val
33
34if __name__ == "__main__":
35 p = "abababc"
36 get_next(p)
输出：
1第 1 趟：
2abababc
3初始化
4[-1, -1, -1, -1, -1, -1, -1]
5第 2 趟：
6abababc
7 abababc
8 ^
9[-1, 0, -1, -1, -1, -1, -1]
10第 3 趟：
11abababc
12 abababc
13 ^
14[-1, 0, 0, -1, -1, -1, -1]
15第 4 趟：
16abababc
17 abababc
18 ^
19[-1, 0, 0, 1, -1, -1, -1]
20第 5 趟：
21abababc
22 abababc
23 ^
24[-1, 0, 0, 1, 2, -1, -1]
25第 6 趟：
26abababc
27 abababc
28 ^
29[-1, 0, 0, 1, 2, 3, -1]
30第 7 趟：
31abababc
32 abababc
33 ^
34[-1, 0, 0, 1, 2, 3, 4]
代码实现
Python实现
1def get_next(p):
2 """求部分匹配表（失配指针）"""
3 i = 0 # 指向主串的指针
4 j = -1 # 指向模式串的指针
5 next_val = [-1] * len(p) # 要返回的next数组
6 # next[0]==-1，只需要求后面的len(p)-1个值即可
7 while i < len(p)-1 and j < len(p)-1:
8 # 匹配成功，相同前缀长度增加1
9 if j == -1 or p[i] == p[j]:
10 i += 1
11 j += 1
12 next_val[i] = j
13 # 匹配不成功则在前面的子串中继续搜索，直至找不到
14 else:
15 j = next_val[j]
16 return next_val
17
18def KMP(s, p):
19 if len(s) < len(p):
20 return -1
21 i, j = 0, 0
22 # 求next数组
23 next = get_next(p)
24 # 匹配阶段
25 while i < len(s) and j < len(p):
26 if j == -1 or s[i] == p[j]:
27 i += 1
28 j += 1
29 else:
30 j = next[j]
31 if j == len(p):
32 return i - j
33 return -1
34
35if __name__ == "__main__":
36 s = "ababababca"
37 p = "abababc"
38 result = KMP(s, p)
39 if result == -1:
40 print("False")
41 else:
42 print(result)
优化代码：去除get_next()，边匹配边计算部分匹配表
1def KMP(s, p):
2 if len(s) < len(p):
3 return -1
4 i, j = 0, 0
5 p_i, p_j = 0, -1
6 next = [-1] * len(p)
7 # 边计算部分匹配表，边匹配
8 while i < len(s) and j < len(p):
9 # 求部分匹配表
10 if p_i < len(p)-1:
11 if p_j == -1 or p[p_i] == p[p_j]:
12 p_i += 1
13 p_j += 1
14 next[p_i] = p_j
15 else:
16 p_j = next[p_j]
17 # 匹配阶段
18 if j == -1 or s[i] == p[j]:
19 i += 1
20 j += 1
21 else:
22 j = next[j]
23 if j == len(p):
24 return i - j
25 return -1
26
27if __name__ == "__main__":
28 s = "ababababca"
29 p = "abababc"
30 result = KMP(s, p)
31 if result == -1:
32 print("False")
33 else:
34 print(result)
C语言
1#include <stdio.h>
2#include <stdlib.h>
3
4int KMP(char s[], int len_s, char p[], int len_p) {
5 if (len_s < len_p)
6 return -1;
7 // 创建和初始化部分匹配表
8 int* next = (int*)malloc(len_p*sizeof(int));
9 for (int i = 0; i < len_p; i++)
10 next[i] = -1;
11 // 边计算部分匹配表，边匹配
12 int i = 0, j = 0, p_i = 0, p_j = -1;
13 while (i < len_s && j < len_p) {
14 // 求部分匹配表
15 if (p_i < len_p-1) {
16 if (p_j == -1 || p[p_i] == p[p_j]) {
17 p_i++;
18 p_j++;
19 next[p_i] = p_j;
20 }
21 else
22 p_j = next[p_j];
23 }
24 // 匹配阶段
25 if (j == -1 || s[i] == p[j]) {
26 i++;
27 j++;
28 }
29 else
30 j = next[j];
31 }
32 free(next);
33 if (j == len_p)
34 return i - j;
35 return -1;
36}
37
38#define LEN(S) sizeof(S)-1
39
40int main(void)
41{
42#define S "ababababca"
43#define P "abababc"
44 char s[sizeof(S)] = S;
45 char p[sizeof(P)] = P;
46 int result = KMP(s, LEN(s), p, LEN(p));
47 if (result == -1)
48 printf("False\n");
49 else
50 printf("%d\n", result);
51 return 0;
52}
评论