c++中如何实现KMP算法_c++ KMP算法实现方法

#include <iostream>
#include <vector>
#include <string>
<p>std::vector<int> buildNext(const std::string& pattern) {
int n = pattern.length();
std::vector<int> next(n, 0);
int j = 0;
for (int i = 1; i < n; ++i) {
while (j > 0 && pattern[i] != pattern[j]) {
j = next[j - 1];
}
if (pattern[i] == pattern[j]) {
++j;
}
next[i] = j;
}
return next;
}</p><p>std::vector<int> kmpSearch(const std::string& text, const std::string& pattern) {
std::vector<int> matches;
if (pattern.empty()) return matches;</p><pre class='brush:php;toolbar:false;'>auto next = buildNext(pattern);
int m = text.length();
int n = pattern.length();
int j = 0;

for (int i = 0; i < m; ++i) {
    while (j > 0 && text[i] != pattern[j]) {
        j = next[j - 1];
    }
    if (text[i] == pattern[j]) {
        ++j;
    }
    if (j == n) {
        matches.push_back(i - n + 1);
        j = next[j - 1]; // 准备下一次匹配
    }
}
return matches;

for (int pos : result) {
    std::cout << "Pattern found at index " << pos << std::endl;
}

return 0;