KMP 算法全剖析：高效实现字符串匹配与模板题详解

在做KMP算法处置惩罚字符串范例题前，可以先参考一下KMP算法原理
下面是笔者写的一个简朴KMP算法示例~

KMP算法模板

1. #include <iostream>
2. #include <vector>
3. using namespace std;
5. // 生成 nextval 数组
6. // nextval 数组是对 next 数组的优化，用于在 KMP 算法中更高效地进行字符串匹配
7. // 它可以避免在匹配过程中进行不必要的回溯
8. vector<int> getNextval(const string& P) {
9.     // 获取模式串 P 的长度
10.     int n = P.size();
11.     // 初始化 nextval 数组，长度为 n，初始值都设为 0
12.     vector<int> nextval(n, 0);
13.     // nextval 数组的第一个元素设为 -1，表示当模式串的第一个字符就不匹配时，主串指针需要后移
14.     nextval[0] = -1;
15.     // j 用于遍历模式串 P，k 用于记录当前最长相等前后缀的长度
16.     int j = 0, k = -1;
17.     // 开始构建 nextval 数组，循环直到 j 遍历到模式串的倒数第二个字符
18.     while (j < n - 1) {
19.         // 如果 k 为 -1 或者当前遍历到的模式串字符 P[j] 等于 P[k]
20.         if (k == -1 || P[j] == P[k]) {
21.             // j 和 k 都向后移动一位
22.             j++; k++;
23.             // 如果 P[j] 不等于 P[k]，则 nextval[j] 就等于 k
24.             // 否则，将 nextval[k] 的值赋给 nextval[j]，避免不必要的回溯
25.             nextval[j] = (P[j] != P[k]) ? k : nextval[k];
26.         } else {
27.             // 如果 P[j] 不等于 P[k]，则将 k 更新为 nextval[k]，继续寻找合适的前后缀
28.             k = nextval[k];
29.         }
30.     }
31.     // 返回构建好的 nextval 数组
32.     return nextval;
33. }
35. // KMP 匹配算法
36. // 在主串 S 中查找模式串 P 第一次出现的位置
37. int kmp(const string& S, const string& P) {
38.     // 调用 getNextval 函数生成模式串 P 的 nextval 数组
39.     vector<int> nextval = getNextval(P);
40.     // i 用于遍历主串 S，j 用于遍历模式串 P
41.     int i = 0, j = 0;
42.     // 获取主串 S 和模式串 P 的长度
43.     int lenS = S.size(), lenP = P.size();
44.     // 开始进行匹配，只要主串和模式串都还没遍历完就继续循环
45.     while (i < lenS && j < lenP) {
46.         // 如果 j 为 -1 或者当前主串字符 S[i] 等于模式串字符 P[j]
47.         if (j == -1 || S[i] == P[j]) {
48.             // 主串和模式串的指针都向后移动一位
49.             i++; j++;
50.         } else {
51.             // 如果不匹配，则将 j 更新为 nextval[j]，根据 nextval 数组进行回溯
52.             j = nextval[j];
53.         }
54.     }
55.     // 如果模式串 P 被完全匹配（j 等于模式串的长度），则返回匹配的起始位置
56.     // 匹配起始位置为 i - j，否则返回 -1 表示未找到匹配
57.     return (j == lenP) ? i - j : -1;
58. }
60. int main() {
61.     // 定义主串 S
62.     string S = "ababaaababaaababaaababaa";
63.     // 定义模式串 P
64.     string P = "ababaaababaa";
65.     // 调用 kmp 函数在主串 S 中查找模式串 P 的位置
66.     int pos = kmp(S, P);
67.     // 输出匹配的位置
68.     cout << "匹配位置: " << pos << endl; // 输出 0
69.     return 0;
70. }

复制代码

洛谷P3375【模板】KMP例题

输入样例

1. ABABABC
2. ABA

复制代码

输出样例

1. 1
2. 3
3. 0 0 1

复制代码

算法思路

本题主要涉及两个核心任务：一是找出字符串 s2 在字符串 s1 中全部出现的位置；二是盘算 s2 每个前缀的最长 border 长度。我们可以使用 KMP（Knuth-Morris-Pratt）算法来高效地完成这两个任务。

• 盘算最长 border 长度（构建 next 数组）
  

• next 数组的界说：next 表示字符串 s2 长度为 i 的前缀的最长 border 长度。
  
• 构建过程：使用双指针法，一个指针 i 用于遍历字符串 s2，另一个指针 j 用于记录当前最长 border 的长度。当 s2=s2[j]时，i 和 j 同时后移；当 s2!=s2[j] 时，j 回溯到 next[j - 1] 的位置继续比较，直到找到匹配或 j 为 0。
  

• 字符串匹配
  

• 利用已经构建好的 next 数组，使用双指针法在 s1 中匹配 s2。一个指针 i 遍历 s1，另一个指针 j 遍历 s2。当 s1=s2[j] 时，i 和 j 同时后移；当 s1!=s2[j] 时，j 回溯到 next[j - 1] 的位置继续比较，直到找到匹配或 j 为 0。当 j 等于 s2 的长度时，说明找到了一个匹配，记录匹配位置并继续匹配。
  

代码示例

1. #include <iostream>
2. #include <vector>
3. #include <string>
5. using namespace std;
7. // 构建 next 数组
8. vector<int> getNext(const string& s) {
9.     int n = s.size();
10.     vector<int> next(n, 0);
11.     for (int i = 1, j = 0; i < n; ++i) {
12.         while (j > 0 && s[i] != s[j]) {
13.             j = next[j - 1];
14.         }
15.         if (s[i] == s[j]) {
16.             ++j;
17.         }
18.         next[i] = j;
19.     }
20.     return next;
21. }
23. // KMP 匹配
24. vector<int> kmp(const string& s1, const string& s2, const vector<int>& next) {
25.     vector<int> positions;
26.     int n1 = s1.size(), n2 = s2.size();
27.     for (int i = 0, j = 0; i < n1; ++i) {
28.         while (j > 0 && s1[i] != s2[j]) {
29.             j = next[j - 1];
30.         }
31.         if (s1[i] == s2[j]) {
32.             ++j;
33.         }
34.         if (j == n2) {
35.             positions.push_back(i - n2 + 1 + 1); // 位置从 1 开始计数
36.             j = next[j - 1];
37.         }
38.     }
39.     return positions;
40. }
42. // 输出匹配位置
43. void printPositions(const vector<int>& positions) {
44.     for (int pos : positions) {
45.         cout << pos << endl;
46.     }
47. }
49. // 输出每个前缀的最长 border 长度
50. void printNext(const vector<int>& next) {
51.     for (int i = 0; i < next.size(); ++i) {
52.         if (i > 0) cout << " ";
53.         cout << next[i];
54.     }
55.     cout << endl;
56. }
58. int main() {
59.     ios::sync_with_stdio(false);
60.     cin.tie(nullptr);
62.     string s1, s2;
63.     cin >> s1 >> s2;
65.     // 构建 next 数组
66.     vector<int> next = getNext(s2);
68.     // 进行 KMP 匹配
69.     vector<int> positions = kmp(s1, s2, next);
71.     // 输出匹配位置
72.     printPositions(positions);
74.     // 输出每个前缀的最长 border 长度
75.     printNext(next);
77.     return 0;
78. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。