KMP算法的完整代码c++
时间: 2024-09-19 13:13:08 浏览: 26
KMP算法(Knuth-Morris-Pratt 算法),用于在文本串中查找指定模式串,它通过预处理模式串构建部分匹配表,避免了不必要的字符比较,提高了搜索效率。以下是KMP算法的基本C++实现:
```cpp
#include <iostream>
#include <vector>
// 定义部分匹配表
std::vector<int> getPartialMatchTable(const std::string& pattern) {
int len = pattern.length();
std::vector<int> lps(len, 0);
int j = 0;
for (int i = 1; i < len; ++i) {
if (pattern[i] == pattern[j]) {
j++;
lps[i] = j;
} else if (j > 0) {
j = lps[j - 1];
} else {
lps[i] = 0;
}
}
return lps;
}
// KMP搜索函数
bool kmpSearch(const std::string& text, const std::string& pattern) {
int n = text.length();
int m = pattern.length();
std::vector<int> lps = getPartialMatchTable(pattern);
int i = 0, j = 0;
while (i < n) {
if (text[i] == pattern[j]) {
i++;
j++;
} else if (j > 0) {
j = lps[j - 1]; // 如果当前字符不匹配,回退到lps[j-1]
} else {
i++; // 如果pattern的第一个字符就不匹配,直接移动text指针
}
if (j == m) { // 找到了模式串
std::cout << "Pattern found at index " << i - j << std::endl;
j = lps[j - 1]; // 为了下次搜索跳过已经匹配过的部分
}
}
return j == 0; // 没有找到模式串则返回false
}
int main() {
std::string text = "ABABDABACDABABC";
std::string pattern = "ABCDAB";
if (kmpSearch(text, pattern)) {
std::cout << "Pattern present in the text." << std::endl;
} else {
std::cout << "Pattern not present in the text." << std::endl;
}
return 0;
}