KMP 算法全剖析：高效实现字符串匹配与模板题详解
在做KMP算法处置惩罚字符串范例题前，可以先参考一下KMP算法原理下面是笔者写的一个简朴KMP算法示例~
https://i-blog.csdnimg.cn/direct/69f8e027506748da8a6d7398ba0fe16c.png
KMP算法模板
#include <iostream>
#include <vector>
using namespace std;
// 生成 nextval 数组
// nextval 数组是对 next 数组的优化，用于在 KMP 算法中更高效地进行字符串匹配
// 它可以避免在匹配过程中进行不必要的回溯
vector<int> getNextval(const string& P) {
// 获取模式串 P 的长度
int n = P.size();
// 初始化 nextval 数组，长度为 n，初始值都设为 0
vector<int> nextval(n, 0);
// nextval 数组的第一个元素设为 -1，表示当模式串的第一个字符就不匹配时，主串指针需要后移
nextval = -1;
// j 用于遍历模式串 P，k 用于记录当前最长相等前后缀的长度
int j = 0, k = -1;
// 开始构建 nextval 数组，循环直到 j 遍历到模式串的倒数第二个字符
while (j < n - 1) {
// 如果 k 为 -1 或者当前遍历到的模式串字符 P 等于 P
if (k == -1 || P == P) {
// j 和 k 都向后移动一位
j++; k++;
// 如果 P 不等于 P，则 nextval 就等于 k
// 否则，将 nextval 的值赋给 nextval，避免不必要的回溯
nextval = (P != P) ? k : nextval;
} else {
// 如果 P 不等于 P，则将 k 更新为 nextval，继续寻找合适的前后缀
k = nextval;
}
}
// 返回构建好的 nextval 数组
return nextval;
}
// KMP 匹配算法
// 在主串 S 中查找模式串 P 第一次出现的位置
int kmp(const string& S, const string& P) {
// 调用 getNextval 函数生成模式串 P 的 nextval 数组
vector<int> nextval = getNextval(P);
// i 用于遍历主串 S，j 用于遍历模式串 P
int i = 0, j = 0;
// 获取主串 S 和模式串 P 的长度
int lenS = S.size(), lenP = P.size();
// 开始进行匹配，只要主串和模式串都还没遍历完就继续循环
while (i < lenS && j < lenP) {
// 如果 j 为 -1 或者当前主串字符 S 等于模式串字符 P
if (j == -1 || S == P) {
// 主串和模式串的指针都向后移动一位
i++; j++;
} else {
// 如果不匹配，则将 j 更新为 nextval，根据 nextval 数组进行回溯
j = nextval;
}
}
// 如果模式串 P 被完全匹配（j 等于模式串的长度），则返回匹配的起始位置
// 匹配起始位置为 i - j，否则返回 -1 表示未找到匹配
return (j == lenP) ? i - j : -1;
}
int main() {
// 定义主串 S
string S = "ababaaababaaababaaababaa";
// 定义模式串 P
string P = "ababaaababaa";
// 调用 kmp 函数在主串 S 中查找模式串 P 的位置
int pos = kmp(S, P);
// 输出匹配的位置
cout << "匹配位置: " << pos << endl; // 输出 0
return 0;
}
洛谷P3375【模板】KMP例题
https://i-blog.csdnimg.cn/direct/d66bfbbed37042ef89c1765d891e378d.png
输入样例
ABABABC
ABA
输出样例
1
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时，i 和 j 同时后移；当 s2!=s2 时，j 回溯到 next 的位置继续比较，直到找到匹配或 j 为 0。
[*]字符串匹配
[*]利用已经构建好的 next 数组，使用双指针法在 s1 中匹配 s2。一个指针 i 遍历 s1，另一个指针 j 遍历 s2。当 s1=s2 时，i 和 j 同时后移；当 s1!=s2 时，j 回溯到 next 的位置继续比较，直到找到匹配或 j 为 0。当 j 等于 s2 的长度时，说明找到了一个匹配，记录匹配位置并继续匹配。
代码示例
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// 构建 next 数组
vector<int> getNext(const string& s) {
int n = s.size();
vector<int> next(n, 0);
for (int i = 1, j = 0; i < n; ++i) {
while (j > 0 && s != s) {
j = next;
}
if (s == s) {
++j;
}
next = j;
}
return next;
}
// KMP 匹配
vector<int> kmp(const string& s1, const string& s2, const vector<int>& next) {
vector<int> positions;
int n1 = s1.size(), n2 = s2.size();
for (int i = 0, j = 0; i < n1; ++i) {
while (j > 0 && s1 != s2) {
j = next;
}
if (s1 == s2) {
++j;
}
if (j == n2) {
positions.push_back(i - n2 + 1 + 1); // 位置从 1 开始计数
j = next;
}
}
return positions;
}
// 输出匹配位置
void printPositions(const vector<int>& positions) {
for (int pos : positions) {
cout << pos << endl;
}
}
// 输出每个前缀的最长 border 长度
void printNext(const vector<int>& next) {
for (int i = 0; i < next.size(); ++i) {
if (i > 0) cout << " ";
cout << next;
}
cout << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s1, s2;
cin >> s1 >> s2;
// 构建 next 数组
vector<int> next = getNext(s2);
// 进行 KMP 匹配
vector<int> positions = kmp(s1, s2, next);
// 输出匹配位置
printPositions(positions);
// 输出每个前缀的最长 border 长度
printNext(next);
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]