#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int ph[N];
char s1[N],s2[N];
int l1,l2;
void init(){
	ph[0]=0;
	for(int i=1;i<l2;i++){
		int j=ph[i-1];
		while(j&&s2[i]!=s2[j])j=ph[j-1];
		if(s2[i]==s2[j])j++;
		ph[i]=j;
	}
}
void KMP(){
	int i=0,j=0;
	while(i<l1){
		while(j&&s1[i]!=s2[j]){
			j=ph[j-1];
		}
		cout<<i<<' '<<j<<endl;
		if(j==l2-1&&s1[i]==s2[j])cout<<i+1-l2+1<<endl,j=ph[j-1];
		i++;
		j++;
	}
}
int main(){
	//freopen("a.in.in","r",stdin);
	cin>>s1;
	cin>>s2;
	l1=strlen(s1); 
	l2=strlen(s2);
	init();
	KMP();
	for(int i=0;i<l2;i++)cout<<ph[i]<<' ';
	return 0; 
}

https://www.luogu.com.cn/record/184589383