KMP字符串匹配

题目传送门

解题思路

这题就是kmp的模板题
百度百科的解释
巨爷myc的“深入浅出”
kmp就是一个时间复杂度为O(n+m)的处理字符串匹配问题的算法

AC代码

#include<iostream>
#include<cstdio>
using namespace std;
int n,ans,len1,len2,next[1000005];
string s1,s2;
void getnext()//求next数组
{
   
	for(int i=1,k=0;i<len2;i++)//定义两个变量
	{
   
		while(k&&s2[i]!=s2[k]) k=next[k-1];//不相等
		if(s2[i]==s2[k]) k++;//相等
		next[i]=k;//赋值
	}
}
void kmp()
{
   
	next[0]=0;//初值
	getnext();
	for(int i=0,k=0;i<len1;i++)//下面同上面神似
	{
   
		while(k&&s1[i]!=s2[k]) k=next[k-1];
		if(s1[i]==s2[k]) k++;
		if(k==len2)
		 printf("%d\n",i-len2+2);
	}
}
int main()
{
   
	cin>>s1;//输入
	cin>>s2;
	len1=s1.size();
	len2=s2.size();
	kmp();
	for(int i=0;i<len2;i++)//输出
	 printf("%d ",next[i]);
	return 0;
}

谢谢