给定一个字符串 text 和一个模式串 pattern，求 pattern 在text 中的出现次数。text 和 pattern 中的字符均为英语大写字母或小写字母。text中不同位置出现的pattern 可重叠。
输入格式:
输入共两行，分别是字符串text 和模式串pattern。
输出格式:
输出一个整数，表示 pattern 在 text 中的出现次数。
输入样例1:
zyzyzyz
zyz
输出样例1:
3
输入样例2:
AABAACAADAABAABA
AABA
输出样例2:
3
数据范围与提示:
1≤text, pattern 的长度 ≤106， text、pattern 仅包含大小写字母。文章来源：https://www.toymoban.com/news/detail-737314.html
#include<stdio.h>
char t[1000001],p[1000001];
int next[1000001],con=0;
int lt=0,lp=0;
void get_next(){
int i=-1,j=0;
next[0]=-1;//这里由于一般下标从1开始但为了简便下标从零开始但赋值为-1
while(j<lp){
if(i==-1||p[j]==p[i]){
i++;
j++;
next[j]=i;//第一次next[1]=0符合公式
}
else i=next[i];
}
}
void kmp(){
int i=0,j=0;
while(i<lt){
//并不是找第一次出现while条件减少主串完即可
if(j==-1||t[i]==p[j]){
i++;
j++;
}
else j=next[j];
if(j==lp)
{
con++;
}
}
}
int main(){
while((t[lt]=getchar())!='\n')lt++;
while((p[lp]=getchar())!='\n')lp++;//这里运行时间pta测试卡的很死，不要用stelen和scanf或gets输入数据
get_next();
kmp();
printf("%d",con);
return 0;
}
详细思想参考【July】从头到尾彻底理解KMP - 阿津 - 博客园 (cnblogs.com)https://www.cnblogs.com/JoBlg/p/4087230.html文章来源地址https://www.toymoban.com/news/detail-737314.html
到了这里，关于PTA 7-1 字符串模式匹配（KMP）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
