【题目描述】
求在主串中模式串重复出现的次数。
题目引申自：https://blog.csdn.net/hnjzsyjyj/article/details/134238575
【输入格式】
第一行输入组数T；
接下来T行数据，其中每行的第一个数据表示模式串（长度≤1000），第二个数据表示主串，用空格隔开。
【输出格式】
输出一个整数，表示在主串中模式串重复出现的次数。
【输入样例】
2
AZAZAZA
AZA
ttYkYtYYk
tY
【输出样例】
3
2
【算法分析】
在本文 KMP 函数的定义中，只需在 if(j==lent) 时，修改 j 的值，便可实现由不重叠（j=0）计算至重叠（j=ne[j]）计算模式串在主串中出现的次数。
题目“HDU 2087：剪花布条”，不重叠计算模式串在主串中出现的次数。（if(j==lent), j=0）
题目“HDU 1686：Oulipo”，重叠计算模式串在主串中出现的次数。（if(j==lent), j=ne[j]）
【算法代码】
#include<bits/stdc++.h>
using namespace std;const int maxn=1e3+5;
int ne[maxn];void getNext(string t) {int len=t.length();int i=0, j=-1;ne[0]=-1;while(i<len) {if(j==-1 || t[i]==t[j]) {i++;j++;ne[i]=j;} else j=ne[j];}
}int KMP(string S,string T) {int lens=S.length();int lent=T.length();int i=0;int j=0;int cnt=0;while(i<lens && j<lent) {if(j==-1 || S[i]==T[j]) {i++;j++;} else j=ne[j];if(j==lent) {cnt++;j=ne[j]; //j=0;}}return cnt;
}int main() {int T;cin>>T;while(T--) {string s,t;cin>>s>>t;getNext(t);cout<<KMP(s,t)<<endl;}return 0;
}/*
input:
2
AZAZAZA
AZA
ttYkYtYYk
tYoutput:
3
2
*/
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/127112363
https://blog.csdn.net/hnjzsyjyj/article/details/127140892
https://blog.csdn.net/hnjzsyjyj/article/details/127112363
https://blog.csdn.net/hnjzsyjyj/article/details/134238575
