luogu P3375 【模板】KMP字符串匹配

模板，代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>

using namespace std;

const int N=1000009;
char s1[N],s2[N];
int nxt[N];

void init()
{
	scanf("%s %s",s1+1,s2+1);
}

void work()
{
	nxt[0]=-1,nxt[1]=0;
	int j=0,len1=strlen(s1+1),len2=strlen(s2+1);
	for (int i=2;i<=len2;i++)
	{
		while(j!=-1&&s2[j+1]!=s2[i])
			j=nxt[j];
		j++;
		nxt[i]=j;
	}
	j=0;
	for (int i=1;i<=len1;i++)
	{
		while(j!=-1&&s2[j+1]!=s1[i])
			j=nxt[j];
		j++;
		if(j==len2)
			printf("%d
",i-len2+1);
	}
	for (int i=1;i<=len2;i++)
		printf("%d ",nxt[i]);puts("");
}

int main()
{
	init();
	work();
	return 0;
}