子串查找

解题思路

这题是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;
}

谢谢