用C++实现数据结构算法4.3用KMP算法计算函数值例题abbabcac的代码
时间: 2024-10-27 08:06:43 浏览: 3
在C++中,KMP算法(Knuth-Morris-Pratt 算法)通常用于字符串匹配问题,包括计算某个模式串在主串中的位置。针对4.3节的例题"abbabcac",我们首先要创建一个next数组存储前缀函数的结果,然后遍历主串查找模式串。以下是一个简单的C++代码实现:
```cpp
#include <iostream>
#include <vector>
// 计算next数组
std::vector<int> get_next(const std::string& pattern) {
int len = pattern.length();
std::vector<int> next(len);
int j = -1;
for (int i = 0; i < len; ++i) {
while (j != -1 && pattern[i] != pattern[j + 1]) {
j = next[j];
}
if (pattern[i] == pattern[j + 1]) {
j++;
}
next[i] = j;
}
return next;
}
// KMP匹配主串
int kmp_search(const std::string& main_str, const std::string& pattern) {
int len_main = main_str.length(), len_pattern = pattern.length();
std::vector<int> next = get_next(pattern);
int index = 0, j = 0;
while (index < len_main) {
if (main_str[index] == pattern[j]) {
index++, j++;
} else if (j != 0) {
j = next[j - 1]; // 如果当前字符不匹配,回溯到next[j - 1]
} else {
index++; // 主串继续匹配下一个字符
}
if (j == len_pattern) { // 找到了匹配的模式
return index - j;
}
}
return -1; // 没有找到匹配
}
int main() {
std::string main_str = "abbabcac";
std::string pattern = "abc";
int result = kmp_search(main_str, pattern);
if (result != -1) {
std::cout << "Pattern found at position " << result << std::endl;
} else {
std::cout << "Pattern not found" << std::endl;
}
return 0;
}
```
在这个例子中,`kmp_search` 函数首先计算了 `pattern` 的前缀函数 `next`,然后遍历 `main_str` 通过比较和回溯操作寻找 `pattern`。如果找到匹配,返回开始位置;否则返回 -1 表示未找到。
阅读全文