刚刚测了一发$O(n^2)$的前缀函数求法，不开O2不加任何优化跑了过去。

#include<stdio.h>
#include<iostream>
using namespace std;
const int maxn=2000005;
int n,m;
int p[maxn];
string a,b,s;
int main(){
	cin>>b>>a;
	s=a+"#"+b;
	p[0]=0;
	for(int i=1;i<s.size();i++){
		for(int j=p[i-1]+1;j>=0;j--)
			if(s.substr(0,j)==s.substr(i-j+1,j)){
				p[i]=j;
				break;
			} 
		if(i>a.size()&&p[i]==a.size())
			printf("%d\n",(i-a.size()+1)-a.size());
	}
	for(int i=0;i<a.size();i++)
		printf("%d%c",p[i],i==a.size()-1? '\n':' ');
	return 0;
}