子串查找（kmp 算法）

子串查找

解題思路

這題是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;
}

           

謝謝