KMP算法
KMP算法作用：字符串匹配
例如母串S = “aaagoogleaaa”;
子串T= “google”;
步骤1：先计算子串中的前后缀数组Next
| g | o | o | g | l | e |
|---|---|---|---|---|---|
| next[0] | next[1] | next[2] | next[3] | next[4] | next[5] |
| -1 | 0 | 0 | 0 | 1 | 0 |
C++代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
//步骤1：void GetNext(string Tsub, vector<int>& Next){ int j = 0, k = -1; Next[0] = k; while (j < Tsub.length() - 1) { if (k == -1 || Tsub[j] == Tsub[k]) { Next[++j] = ++k; } else { k = Next[k]; } }} |
步骤2：查找子串在母串中出现的位置。
|
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
|
//步骤2：int KMP(string S, string T, vector<int> Next){ int i = 0, j = 0; int m = S.length(); int n = T.length(); while (i < m && j < n) { if (j == -1 || S[i] == T[j]) { i++; j++; } else { j = Next[j]; } } if (j == n) { return i - j; } else { return -1; }} |
结合上面两个步骤写出完整代码：
|
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
|
#include <iostream>#include <vector>using namespace std;//步骤1：void GetNext(string Tsub, vector<int>& Next){ int j = 0, k = -1; Next[0] = k; while (j < Tsub.length() - 1) { if (k == -1 || Tsub[j] == Tsub[k]) { Next[++j] = ++k; } else { k = Next[k]; } }}//步骤2：int KMP(string S, string T, vector<int> Next){ int i = 0, j = 0; int m = S.length(); int n = T.length(); while (i < m && j < n) { if (j == -1 || S[i] == T[j]) { i++; j++; } else { j = Next[j]; } } if (j == n) { return i - j; } else { return -1; }}int main(){ string S = "aaagoogleaaa"; string T = "google"; vector<int> Next(T.length()); GetNext(T, Next); int retVal = KMP(S, T, Next); if (retVal == -1) { std::cout << "can't Index" << std::endl; } else { std::cout << "Index :" << retVal << std::endl; } return 0;} |
总结
本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注服务器之家的更多内容！
原文链接：https://blog.csdn.net/m0_49939824/article/details/119708086
