详细见此 求dalao帮蒟蒻看看。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;

char t[N],p[N];


void getNext(char *p ,int *next)
{
	next[0]=-1;
	int i=0,j=-1;
	while(i<strlen(p))
	{
		if(j==-1 or p[i]==p[j])
		{
			i++; j++;
			next[i]=j;
		}
		else 
			j=next[j];
	}
}
int nex[N];

int KMP(char *t, char *p)
{
	int i=0,j=0;
	
	while(i<strlen(t) and j<strlen(p))
	{
		if(j==-1 or t[i]==p[j])
		{
			i++;j++;
		}
		else 
			j=nex[j];
		if(j==strlen(p))
		{
			cout<<i-j+1<<endl;
			j=nex[j];
		}
			
	}
}
int main()
{
	cin>>t>>p;
	getNext(p,nex);
	KMP(t,p);
	
	for(int i=1;i<=strlen(p);i++)
		cout<<nex[i]<<' ';
}