#include<bits/stdc++.h>
using namespace std;
int KMP(string str,string p)
{ int count = 0;
int k=-1,j=0,next[p.length()];
next[0]= -1;
while(j<p.length())
if(k==-1||p[j]==p[k])
next[++j] = ++k;
else k=next[k];
int q=0,e=0;
while(e<p.length())
{ if(p[e]==str[q])
{
e++;
q++;
}
else e=next[e];
if(e==-1)
{
e++;
q++;
}
if(q>=str.length()&&e<p.length())return count;
else if(q>=str.length()&&e>=p.length())return count+1;
else if(q<str.length()&&e>=p.length())
{
count++;
q=q-e+1;
e=0;
}
}
}
int main()
{
string str,p;
cin>>str>>p;
printf("%d",KMP(str,p));
system("pause");
}
题目是
子串查找
Description
给定一个字符串AA和一个字符串BB，求BB在AA中的出现次数。AA和BB中的字符均为英语大写字母或小写字母。
AA中不同位置出现的BB可重叠。
Input
输入共两行，分别是字符串AA和字符串BB 。
Output
输出一个整数，表示BB在AA中的出现次数。
Sample Input 1
zyzyzyz
zyz
1≤A,B的长度≤10^6 AA、BB仅包含大小写字母。
先判断后循坏比较好，望采纳，不懂的可以关注私信我。
已经改好了
kmp的next数组的理由也有点问题
谢谢啦