给定一个字符串 text 和一个模式串 pattern，求 pattern 在text 中的出现次数。text 和 pattern 中的字符均为英语大写字母或小写字母。text中不同位置出现的pattern 可重叠。
输入格式:
输入共两行，分别是字符串text 和模式串pattern。
输出格式:
输出一个整数，表示 pattern 在 text 中的出现次数。
输入样例1:
zyzyzyz
zyz
输出样例1:
3
输入样例2:
AABAACAADAABAABA
AABA
输出样例2:
3
完全代码：
点击查看代码
#include <iostream>
#include <cstring>
using namespace std;
void getNext(const string& pattern, int* Next) {
Next[0] = -1;
int i = 0, j = -1;
int m = pattern.size();
while (i < m) {
if (j == -1 || pattern[i] == pattern[j]) {
i++;
j++;
Next[i] = j;
} else {
j = Next[j];
}
}
}
int kmp(const string& text, const string& pattern) {
int n = text.size(), m = pattern.size();
if (n < m) return 0; // 如果文本串长度小于模式串，直接返回0
int Next[m + 1];
getNext(pattern, Next);
int count = 0;
int i = 0, j = 0;
while (i < n) {
if (j == -1 || text[i] == pattern[j]) {
i++;
j++;
} else {
j = Next[j];
}
if (j == m) { // 找到一个匹配
count++;
j = Next[j];
}
}
return count;
}
int main() {
string text, pattern;
cin >> text >> pattern;
cout << kmp(text, pattern) << endl;
return 0;
}