子串查找
解题思路
这题是kmp算法模板题
做法同P3375 【模板】KMP字符串匹配(kmp)差不多
我这里k的初值为-1
AC代码
#include<iostream>
#include<cstdio>
using namespace std;
int len1,len2,ans,next[1000005];
string A,B;
void getnext()//求next数组
{
int k=-1;//初值
for(int i=1;i<len2;i++)
{
while(k>-1&&B[k+1]!=B[i])k=next[k];//不相等
if(B[k+1]==B[i])k++;//相等
next[i]=k;//赋值
}
}
void kmp()
{
next[0]=-1;//初值
getnext();
int k=-1;
for(int i=0;i<len1;i++)
{
while(k>-1&&B[k+1]!=A[i])k=next[k];//不相等
if(B[k+1]==A[i])k++;//相等
if(k==len2-1)//判断
{
ans++;
k=next[k];
}
}
}
int main()
{
cin>>A;//输入
cin>>B;
len1=A.size();
len2=B.size();
kmp();
printf("%d",ans);//输出
return 0;
}