您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
KMP算法(Knuth-Morris-Pratt算法)是一种用于字符串匹配的算法,用于在一个文本串中查找一个模式串的出现位置。KMP算法的主要思想是利用已经匹配过的信息来尽量减少比较的次数。
以下是一个简单的C++实现KMP字符串匹配的示例代码:
#include <iostream>
#include <vector>
void computeLPSArray(std::string pattern, std::vector<int>& lps) {
int M = pattern.length();
int len = 0;
lps[0] = 0;
int i = 1;
while (i < M) {
if (pattern[i] == pattern[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}
}
void KMP(std::string text, std::string pattern) {
int N = text.length();
int M = pattern.length();
std::vector<int> lps(M, 0);
computeLPSArray(pattern, lps);
int i = 0, j = 0;
while (i < N) {
if (pattern[j] == text[i]) {
i++;
j++;
}
if (j == M) {
std::cout << "Pattern found at index " << i - j << std::endl;
j = lps[j - 1];
} else if (i < N && pattern[j] != text[i]) {
if (j != 0) {
j = lps[j - 1];
} else {
i++;
}
}
}
}
int main() {
std::string text = "ABABDABACDABABCABAB";
std::string pattern = "ABABCABAB";
KMP(text, pattern);
return 0;
}
在上面的代码中,computeLPSArray
函数用于计算模式串的最长前缀后缀数组(LPS),KMP
函数用于在文本串中查找模式串的出现位置。通过以上代码,您可以在C++中实现KMP算法来进行字符串匹配。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。