题解
2023-07-17 18:45:20
发布于:广东
#include <iostream>
#include <vector>
using namespace std;
void computeLPS(string p, vector<int>& lps) {
int m = p.length();
int len = 0;
int i = 1;
lps[0] = 0;
while (i < m) {
if (p[i] == p[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}
}
int KMP(string s, string p) {
int n = s.length();
int m = p.length();
vector<int> lps(m, 0);
computeLPS(p, lps);
int i = 0;
int j = 0;
int count = 0;
while (i < n) {
if (s[i] == p[j]) {
i++;
j++;
}
if (j == m) {
count++;
j = lps[j - 1];
} else if (i < n && s[i] != p[j]) {
if (j != 0) {
j = lps[j - 1];
} else {
i++;
}
}
}
return count;
}
int main() {
string s, p;
cin >> s >> p;
int count = KMP(s, p);
cout << count << endl;
return 0;
}
这里空空如也
有帮助,赞一个