写个kmp代码
时间: 2023-07-02 22:06:02 浏览: 43
下面是 KMP 算法的 C++ 实现:
```cpp
#include <iostream>
#include <vector>
#include <string>
void kmp(const std::string& text, const std::string& pattern, std::vector<int>& matches) {
int n = text.size();
int m = pattern.size();
// 构建 pattern 的前缀表
std::vector<int> pi(m, 0);
for (int i = 1, j = 0; i < m; ++i) {
while (j > 0 && pattern[i] != pattern[j]) {
j = pi[j - 1];
}
if (pattern[i] == pattern[j]) {
++j;
}
pi[i] = j;
}
// 匹配
for (int i = 0, j = 0; i < n; ++i) {
while (j > 0 && text[i] != pattern[j]) {
j = pi[j - 1];
}
if (text[i] == pattern[j]) {
++j;
}
if (j == m) {
matches.push_back(i - j + 1);
j = pi[j - 1];
}
}
}
int main() {
std::string text = "ABABDABACDABABCABAB";
std::string pattern = "ABABCABAB";
std::vector<int> matches;
kmp(text, pattern, matches);
std::cout << "Matches found at positions: ";
for (int i : matches) {
std::cout << i << " ";
}
std::cout << std::endl;
return 0;
}
```
输出结果为:
```
Matches found at positions: 10
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)