KMP

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000007;
char a[MAXN],b[MAXN];
int la,lb;
int nxt[MAXN];
int main(){
	cin>>a+1;la=strlen(a+1);
	cin>>b+1;lb=strlen(b+1);
	nxt[1]=0;
	int j=0;
	for(int i=2;i<=lb;i++){
		while(j&&b[i]!=b[j+1])j=nxt[j];
		j+=b[i]==b[j+1];
		nxt[i]=j;
	}
	j=0;
	for(int i=1;i<=la;i++){
		while(j&&a[i]!=b[j+1])j=nxt[j];
		j+=a[i]==b[j+1];
		if(j==lb){
			printf("%d
",i-lb+1);
			j=nxt[j];
		}
	}
	for(int i=1;i<=lb;i++)printf("%d ",nxt[i]);
	return 0;
}