KMP模板

#include<bits/stdc++.h>
using namespace std;
int next[1000010],n,l1,l2;
char s1[1000010],s2[1000010];
vector<int> res;
void get_next(char *s)
{
	next[0]=next[1]=0;
	int len=strlen(s+1);
	for(int i=2,j=0;i<=len;i++)
	{
		while(j&&s[i]!=s[j+1])	j=next[j];
		if(s[j+1]==s[i])	j++;
		next[i]=j;
	}
}
void kmp()
{
	get_next(s2);
	for(int i=1,j=0;i<=l1;i++)
	{
		while(j&&(j==n||s1[i]!=s2[j+1]))	j=next[j];
		if(s1[i]==s2[j+1])	j++;
		if(j==l2)	res.push_back(i-j+1),j=next[j];
	}
}
int main()
{
	scanf("%s %s",s1+1,s2+1);
	l1=strlen(s1+1),l2=strlen(s2+1);
	kmp();
	for(int i=0;i<res.size();i++)	cout<<res[i]<<endl;
	for(int i=1;i<=l2;i++)	cout<<next[i]<<' ';
	cout<<endl;
	return 0;
}