传送门

FFT竟然还能解决字符串问题..

但是这个数据好像太水了，KMP瞎搞搞就能过。

考虑一下，如果不考虑问号，那么一个点匹配肯定存在的是$\sum (s1_i-s2_j)^2=0$，那么考虑存在？的情况。很显然，改成这样的即可：

$\sum (s1_i-s2_j)^2 s2_j$

化开即为$\sum s1_i^2s2_j+s2_j^3-2 \times s1_is2_j^2$

可以把$s2$reverse，然后$[M-1,N-1]$即为答案。

//BZOJ4503//by Cydiater//2017.2.11#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <queue>#include <map>#include <cstdlib>#include <cmath>#include <ctime>#include <iomanip>#include <algorithm>#include <bitset>#include <set>#include <vector>#include <complex>using namespace std;  #define ll 		long long#define up(i,j,n)	for(int i=j;i<=n;i++)#define down(i,j,n)	for(int i=j;i>=n;i--)#define cmax(a,b)	a=max(a,b)#define cmin(a,b)	a=min(a,b)#define db 		double#define Plur		complex<double>const int MAXN=5e5+5;const int oo=0x3f3f3f3f;const db PI=acos(-1);char s1[MAXN],s2[MAXN];Plur A[MAXN],B[MAXN],A2[MAXN],B2[MAXN],P1[MAXN],P2[MAXN],P3[MAXN];int N,M,NM,ans=0;namespace FFT{	Plur omega[MAXN],Invomega[MAXN];	void Prepare(int LIM){		up(i,0,LIM-1){			omega[i]=Plur(cos(2*PI*i/LIM),sin(2*PI*i/LIM));			Invomega[i]=conj(omega[i]);		}	}	void Transform(int N,Plur *A,Plur *w){		int pos=0;		up(i,0,N-1){			if(pos<i)swap(A[i],A[pos]);			for(int tmp=N>>1;(pos^=tmp)<tmp;tmp>>=1);		}		for(int l=2;l<=N;l<<=1){			int delta=l>>1;			for(int j=0;j<N;j+=l)up(k,0,delta-1){				Plur tmp=A[j+k+delta]*w[N/l*k];				A[j+delta+k]=A[j+k]-tmp;				A[j+k]+=tmp;			}		}	}	void DFT(int N,Plur *A){		Transform(N,A,omega);	}	void IDFT(int N,Plur *A){		Transform(N,A,Invomega);		up(i,0,N-1)A[i]/=N;	}}namespace solution{	void Prepare(){		scanf("%s",s1);scanf("%s",s2);		N=strlen(s1);M=strlen(s2);		reverse(s2,s2+M);		NM=N+M-1;		up(i,0,M-1)if(s2[i]==‘?‘)s2[i]=‘a‘-1;		int ind=0;		while((1<<ind)<NM)ind++;		NM=(1<<ind);		up(i,0,N-1)A[i].real(s1[i]-‘a‘+1);		up(i,0,N-1)A2[i].real((s1[i]-‘a‘+1)*(s1[i]-‘a‘+1));		up(i,0,M-1)B[i].real(s2[i]-‘a‘+1);		up(i,0,M-1)B2[i].real((s2[i]-‘a‘+1)*(s2[i]-‘a‘+1));	}	int col(int pos){return (int)(P1[pos].real()+P2[pos].real()-P3[pos].real()-P3[pos].real()+0.5);}	void Solve(){		FFT::Prepare(NM);		FFT::DFT(NM,A);FFT::DFT(NM,A2);		FFT::DFT(NM,B);FFT::DFT(NM,B2);		up(i,0,NM-1)P1[i]=A2[i]*B[i];		up(i,0,NM-1)P3[i]=A[i]*B2[i];		FFT::IDFT(NM,P1);		FFT::IDFT(NM,P3);		int tmp=0;		up(i,0,M-1)tmp+=(s2[i]-‘a‘+1)*(s2[i]-‘a‘+1)*(s2[i]-‘a‘+1);		up(i,0,NM-1)P2[i].real(tmp);		up(i,M-1,N-1)if(col(i)==0)ans++;		cout<<ans<<endl;		up(i,M-1,N-1)if(col(i)==0){			printf("%d\n",i-(M-1));		}	}}int main(){	//freopen("input.in","r",stdin);	using namespace solution;	Prepare();	Solve();	return 0;}

BZOJ4503: 两个串