这是一道模板题。
给定一个字符串 AA 和一个字符串 BB，求 BB 在 AA 中的出现次数。AA 和 BB 中的字符均为英语大写字母或小写字母。
AA 中不同位置出现的 BB 可重叠。
Input
输入共两行，分别是字符串 AA 和字符串 BB。
Output
输出一个整数，表示 BB 在 AA 中的出现次数。
Example
样例输入
zyzyzyz
zyz
样例输出
3
Hint
1≤A,B 的长度 ≤106，A、B 仅包含大小写字母。#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stack>
using namespace std;
const int maxn=1e6+10;
string s,p;
int next[maxn];
void getnext(string p){next[0]=-1;int j=0,k=-1;while (j<p.length()- 1){if (k==-1||p[j]==p[k]){j++;k++;next[j] = k;}else k=next[k];}
}
int kmp(string s,string p){getnext(p);int i=0,j=0;int res=0;while(i<s.length()){if(j==-1||s[i]==p[j]){i++;j++;}else j=next[j];if(j==p.length()){ res++; i--; j--; j=next[j]; }}return res;
}
int main(){cin>>s>>p;cout<<kmp(s, p)<<endl;return 0;
}