【模板】KMP

#include<bits/stdc++.h>
using namespace std;
char s1[1000000],s2[1000010]; 
int next[1000010];
void get_next(char s2[])
{
	int i=0,k=-1;
	int len2=strlen(s2);
	next[0]=-1;
	while(i<len2)
	{
		while(k>=0&&s2[i]!=s2[k])k=next[k];
		i++;
		k++;
		next[i]=k;
	} 
	return;
} 
void search(char s1[],char s2[])
{
	int i=0,j=0,match=-1;
	int len1=strlen(s1);
	int len2=strlen(s2);
	while(i<len1)
	{
		if(j==-1||s1[i]==s2[j])i++,j++;
		else j=next[j];
		if(j==len2)
		{
			printf("%d\n",i-len2+1);
		}
	}
	return;
}
int main()
{
	scanf("%s%s",&s1,&s2);
	get_next(s2);
	search(s1,s2);
	int lenx=strlen(s2);
	for(int i=1;i<=lenx;i++)printf("%d ",next[i]);
	return 0;
}