kmp失败函数及kmp算法
作者:
只怪我平庸至极
,
2023-05-04 17:30:04
,
所有人可见
,
阅读 207
kmp失效函数
kmp算法
#include <iostream>
#include <vector>
using namespace std;
vector<int> get_fail(const string& p) {
vector<int> fail(p.size(), -1);
int j = -1;
for (int i = 1; i < p.size(); i++) {
while (j != -1 && p[i] != p[j+1]) {
j = fail[j];
}
if (p[i] == p[j+1]) {
j++;
}
fail[i] = j;
}
return fail;
}
int kmp(const string& s, const string& p) {
vector<int> fail = get_fail(p);
int j = -1;
for (int i = 0; i < s.size(); i++) {
while (j != -1 && s[i] != p[j+1]) {
j = fail[j];
}
if (s[i] == p[j+1]) {
j++;
}
if (j == p.size()-1) {
return i-j;
}
}
return -1;
}
int main() {
string s, p;
cin >> s >> p;
vector<int> fail = get_fail(p);
for (int i = 0; i < fail.size(); i++) {
cout << fail[i] << " ";
}
cout << endl << kmp(s, p) << endl;
return 0;
}