C++11(clang++ 3.9) 解法, 执行用时: 244ms, 内存消耗: 19836K, 提交时间: 2018-07-27 11:42:24

#include<bits/stdc++.h>
using namespace std;

#define Death Komachi 
#define Uni :All right
#define REP(i,a,b) for(int i=(a),i##_end_=(b);i<i##_end_;++i)
#define DREP(i,a,b) for(int i=(a),i##_end_=(b);i>i##_end_;--i)
#define LL long long
#define M 540004
#define Mod 998244353

int Rev[M],W[M],s,t;
char X[M],Y[M],P[44];
int n,m,A[3][M],B[3][M];
int S[M],Ans[M],cnt;
int Pow(int k,int p){
	int Res=1;
	for(;p;k=(LL)k*k%Mod,p>>=1)if(p&1)Res=(LL)Res*k%Mod;
	return Res;
}
void Rever(){
	REP(i,0,s)
		Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(t-1));
}
void DFT(int *A,int p){
	W[0]=1;
	REP(i,0,s)if(i<Rev[i])swap(A[i],A[Rev[i]]);
	for(int i=1,pi=2;i<s;i<<=1,pi<<=1){
		int wn=Pow(3,(Mod-1)/pi);
		if(p)wn=Pow(wn,Mod-2);
		for(int j=i-2;j>=0;j-=2)W[j+1]=(LL)(W[j]=W[j>>1])*wn%Mod;
		for(int j=0;j<s;j+=pi){
			int *L=A+j,*R=A+j+i;
			REP(k,0,i){
				LL Tmp=(LL)R[k]*W[k];
				R[k]=(L[k]-Tmp)%Mod;
				L[k]=(L[k]+Tmp)%Mod;
			}
		}
	}
	if(p){
		int Inv=Pow(s,Mod-2);
		REP(i,0,s)A[i]=(LL)A[i]*Inv%Mod;
	}
}

int main(){
	scanf("%s%s%s",X,Y,P),n=strlen(X),m=strlen(Y);
	reverse(X,X+n);
	REP(i,0,n){
		A[0][i]=X[i]=P[X[i]-'a']-'a';
		REP(j,1,3)A[j][i]=A[j-1][i]*A[0][i];
	}
	REP(i,0,m){
		B[0][i]=Y[i]=P[Y[i]-'a']-'a';
		REP(j,1,3)B[j][i]=B[j-1][i]*B[0][i];
	}
	for(s=1,t=0;s<n+m-1;s<<=1,t++);
	Rever();

	REP(i,0,3)DFT(A[i],0),DFT(B[i],0);
	REP(i,0,s)
		S[i]=(-4ll*A[2][i]*B[0][i]%Mod-4ll*A[0][i]*B[2][i]%Mod+6ll*A[1][i]*B[1][i]%Mod+2ll*A[0][i]*B[0][i]%Mod)%Mod;
	DFT(S,1);
	
	LL Sum=0;
	REP(i,0,n){
		Sum+=((int)X[i]*X[i]-1)*X[i]*X[i];
		Sum+=((int)Y[i]*Y[i]-1)*Y[i]*Y[i];
	}
	REP(i,n-1,m){
		if(!((Sum+S[i])%Mod))Ans[cnt++]=i-n+2;
		Sum+=((int)Y[i+1]*Y[i+1]-1)*Y[i+1]*Y[i+1];
		Sum-=((int)Y[i-n+1]*Y[i-n+1]-1)*Y[i-n+1]*Y[i-n+1];
	}
	printf("%d\n",cnt);
	REP(i,0,cnt)printf("%d%c",Ans[i]," \n"[i==cnt-1]);
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 806ms, 内存消耗: 24804K, 提交时间: 2018-07-26 17:27:43

#include<bits/stdc++.h>
#define pi acos(-1.0)
#define N 262144
#define L 250005
#define eps 1e-8
using namespace std;
struct node {
	double x,y;
}ans[N],A[N],B[N],w[2][N];
int i,j,k,l,s,n,m,M,rev[N];
int Ans,da[L];
char c[L],c1[L],T[27];
inline node operator + (node a,node b) { return (node) {a.x+b.x,a.y+b.y};}
inline node operator - (node a,node b) { return (node) {a.x-b.x,a.y-b.y};}
inline node operator * (node a,node b) { return (node) {a.x*b.x-a.y*b.y,a.x*b.y+b.x*a.y};}
inline void pre() {
	for (int i=0;i<M;i++) {
		int j=i,y=0;
		for (int x=1;x<M;x<<=1,j>>=1) (y<<=1)+=j&1;
		rev[i]=y;
	}
	for (int i=0;i<M;i++) w[0][i]=(node){cos(2*pi*i/M),sin(2*pi*i/M)},w[1][i]=(node){cos(2*pi*i/M),-sin(2*pi*i/M)};
}
inline void FFT(node *A,int p) {
	for (int i=0;i<M;i++) if (i<rev[i]) swap(A[i],A[rev[i]]);
	for (int i=1;i<M;i<<=1) 
	for (int j=0,t=M/(i<<1),o=i<<1;j<M;j+=o)
	for (int k=0,l=0;k<i;k++,l+=t) {
		node x=w[p][l]*A[i+j+k];
		node y=A[j+k];
		A[j+k]=y+x;
		A[j+k+i]=y-x;
	}
	if (p) for (int i=0;i<M;i++) A[i].x/=M;
}
int main() {
	scanf("%s%s",c,c1);
	scanf("%s",T);
	
	n=strlen(c),m=strlen(c1);
	for (i=0;i<n;i++) c[i]=T[c[i]-'a'];
	for (i=0;i<m;i++) c1[i]=T[c1[i]-'a'];
	for (M=1;M<=m;M<<=1);
	pre();	
	for (i=0;i<26;i++) {
		for (k=0;k<n;k++) if (c[k]-97==i) A[n-k].x=1;
		else A[n-k].x=0;
		for (k=0;k<m;k++) if (abs(c1[k]-97-i)<=1) B[k].x=1;
		else B[k].x=0;
		FFT(A,0),FFT(B,0);
		for (k=0;k<M;k++) ans[k]=ans[k]+A[k]*B[k],A[k].x=A[k].y=B[k].x=B[k].y=0;
	}
	FFT(ans,1);
	for (i=n;i<M;i++) if (ans[i].x+eps>=n) da[++Ans]=i-n+1;
	printf("%d\n",Ans);
	for (i=1;i<=Ans;i++) printf("%d ",da[i]);
	puts("");
}