●Codevs 4158 残缺的字符串

题链：

http://codevs.cn/problem/4158/

题解：

FFT。

定义两个相同长度的字符串s1,s2的距离为

$$dis(s1,s2)=\sum_{i=0}^{len-1}(s1[i]-s2[i])^2s1[i]s2[i]$$

如果两个字符串相同，那么dis=0。

（对于本题而言，只需把通配符用0表示，其它字符c用c-'a'+1表示。）

然后看看如何求出文本串T(长度为n)和模式串S(长度为m)的总共匹配数。

定义T串从$l$位置开始的长度为m的子串和S的距离为$D(l)$，那么：

$$D(l)=\sum_{k=0}^{m-1}(T[l+k]-S[k])^2T[l+k]S[k]$$

为了构成卷积形式，我们把S串翻转，即

$$D(l)=D'(l+m-1)=\sum_{k=0}^{m-1}(T[l+k]-S[m-1-k])^2T[l+k]S[m-1-k]$$

然而这个仍然不是卷积形式，我们再继续化一下式子：(令D(l)=D'(l+m-1))

$$\begin{aligned}
D'(l+m-1)&=\sum_{k=0}^{m-1}(T[l+k]-S[m-1-k])^2T[l+k]S[m-1-k]\\
&=\sum_{k=0}^{m-1}(T[l+k]^3S[m-1-k]-2T[l+k]^2S[m-1-k]^2+T[l+k]S[m-1-k]^3)\\
&=\sum_{k=0}^{m-1}T[l+k]^3S[m-1-k]+\sum_{k=0}^{m-1}-2T[l+k]^2S[m-1-k]^2+\sum_{k=0}^{m-1}T[l+k]S[m-1-k]^3
\end{aligned}$$

然后逮着这个式子做3组卷积即可。

代码：

#include<bits/stdc++.h>

#define MAXN 1048577

#define INF 0x3f3f3f3f

using namespace std;

const double Pi=acos(-1),eps=1e-6;

typedef complex<double>Complex;

Complex null(0,0);

int A[MAXN],B[MAXN],order[MAXN];

int idx(char ch){

	if(ch=='*') return 0;

	return ch-'a'+1;

}

void getstring(int *s,int len){

	static char ch;

	for(int i=0;i<len;i++)

		scanf(" %c",&ch),s[i]=idx(ch);

}

void FFT(Complex *Y,int n,int sign){

	for(int i=1;i<n;i++) if(i<order[i]) swap(Y[i],Y[order[i]]);

	for(int d=2;d<=n;d<<=1){

		Complex dw(cos(2*Pi/d),sin(sign*2*Pi/d)),w,tmp;

		for(int i=0;w=Complex(1,0),i<n;i+=d)

			for(int k=i;k<i+d/2;w=w*dw,k++)

				tmp=w*Y[k+d/2],Y[k+d/2]=Y[k]-tmp,Y[k]=Y[k]+tmp;

	}

}

int main(){

	static int pos[MAXN];

	static Complex f1[MAXN],g1[MAXN],f2[MAXN],g2[MAXN],f3[MAXN],g3[MAXN],D[MAXN];

	int n,m,N,len,ans=0; scanf("%d%d",&n,&m);

	getstring(A,n); getstring(B,m); reverse(A,A+n);

	for(N=1,len=0;N<n+m-1;N<<=1) len++;

	for(int i=1;i<N;i++) order[i]=(order[i>>1]>>1)|((i&1)<<(len-1));

	for(int i=0;i<n;i++){

		f1[i]=Complex(A[i]*A[i]*A[i],0);

		f2[i]=Complex(A[i]*A[i],0);

		f3[i]=Complex(A[i],0);

	}

	for(int i=0;i<m;i++){

		g1[i]=Complex(B[i],0);

		g2[i]=Complex(B[i]*B[i],0);

		g3[i]=Complex(B[i]*B[i]*B[i],0);

	}

	FFT(f1,N,1); FFT(g1,N,1);

	FFT(f2,N,1); FFT(g2,N,1);

	FFT(f3,N,1); FFT(g3,N,1);

	for(int i=0;i<N;i++) D[i]=f1[i]*g1[i]-2.0*f2[i]*g2[i]+f3[i]*g3[i];

	FFT(D,N,-1);

	for(int i=0;i<m-n+1;i++)

		if((int)((D[i+n-1].real()+0.5)/N)==0) pos[++ans]=i+1;

	printf("%d\n",ans);

	for(int i=1;i<=ans;i++) printf("%d ",pos[i]);

	printf("\n");

	return 0;

}