本题是一个典型的字符串匹配问题，并且还需要求出前缀和后缀相等的最大长度，这正是ne数组的定义，所以下面使用的是kmp算法的模式匹配，其关键是ne数组，这样回退的时候子串就不需要回退到第一个，提高了查找的效率。

#include<bits/stdc++.h>
using namespace std;
int slen,tlen;
int ne[1000000+5];

void get_next(string t){//求模式串T的next函数值
	int j=0,k=-1;
	ne[0]=-1; 
	while(j<tlen){//模式串t的长度
		if(k==-1||t[j]==t[k])
			ne[++j]=++k;
		else
			k=ne[k];
	}
}

void KMP(string s,string t){
	int i=0,j=0;
	slen=s.length();
	tlen=t.length();
	get_next(t);
	while(i<slen){
        if(j==-1||s[i]==t[j]){//如果相等，则继续比较后面的字符
			i++;
			j++;
		}
		else
			j=ne[j]; //j回退到next[j]
		if(j==tlen){ //匹配成功
			cout<<i-tlen+1<<endl;
			j=ne[j];//不允许重叠，j从0重新开始，如果允许重叠，j=nex[j]
		}
	}
}

int main(){
	string s,t;
	cin>>s>>t;
	KMP(s,t);
	for(int i=1;i<=tlen;i++)
		cout<<ne[i]<<" ";
	return 0;
}