题目
Description
很久很久以前，在你刚刚学习字符串匹配的时候，有两个仅包含小写字母的字符串A和B，其中A串长度为m，B串长度为n。可当你现在再次碰到这两个串时，这两个串已经老化了，每个串都有不同程度的残缺。
你想对这两个串重新进行匹配，其中A为模板串，那么现在问题来了，请回答，对于B的每一个位置i，从这个位置开始连续m个字符形成的子串是否可能与A串完全匹配?
Input
第一行包含两个正整数m,n(1<=m<=n<=300000)，分别表示A串和B串的长度。
第二行为一个长度为m的字符串A。
第三行为一个长度为n的字符串B。
两个串均仅由小写字母和号组成，其中号表示相应位置已经残缺。
Output
第一行包含一个整数k，表示B串中可以完全匹配A串的位置个数。
若k>0，则第二行输出k个正整数，从小到大依次输出每个可以匹配的开头位置（下标从1开始）。
Sample Input
3 7
a*b
aebr*ob
Sample Output
2
1 5
题解
以前写的被$ban$掉了……
把*定义为$0$，求$\sum_{i=0}^{n}(S_{n-i+j}-T_i)^2T_iS_{n-i+j}$是否为$0$
展开后就是$\sum_{i=0}^{n}{S_{n-i+j}}^3T_i+{T_i}^3S_{n-i+j}-2{T_i}^2{S_{n-i+j}}^2$
$FFT$三个卷积就行了
貌似有点卡精度……？
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<cmath>
# include<algorithm>
using namespace std;
const int MAX=1.2e6+5;
const double Pi=acos(-1.0);
struct Complex{
double x,y;
Complex(double X=0,double Y=0) {x=X,y=Y;}
}a[MAX],b[MAX];
int n,m,lim=1,L,ans;
int R[MAX],id[MAX];
double val[MAX];
char A[MAX],B[MAX];
Complex operator+ (Complex x,Complex y) {return Complex(x.x+y.x,x.y+y.y);}
Complex operator- (Complex x,Complex y) {return Complex(x.x-y.x,x.y-y.y);}
Complex operator* (Complex x,Complex y) {return Complex(x.x*y.x-x.y*y.y,x.y*y.x+x.x*y.y);}
void FFT(Complex *A,int tt=1)
{
for(int i=0;i<lim;++i)
if(i<R[i]) swap(A[i],A[R[i]]);
for(int i=1;i<lim;i<<=1)
{
Complex w1=Complex(cos(Pi/i),tt*sin(Pi/i));
for(int l=i<<1,j=0;j<lim;j+=l)
{
Complex w=Complex(1,0),x,y;
for(int k=0;k<i;++k,w=w*w1)
x=A[j+k],y=w*A[i+j+k],A[j+k]=x+y,A[i+j+k]=x-y;
}
}
}
int main()
{
scanf("%d%d%s%s",&n,&m,A,B);
reverse(A,A+n);
while(lim<=n+m-2) lim<<=1,++L;
for(int i=0;i<=lim;++i)
R[i]=(R[i>>1]>>1)|((i&1)<<L-1);
for(int i=0;i<n;++i)
if(A[i]!='*') a[i].x=(A[i]-'a'+1);
for(int i=0;i<m;++i)
if(B[i]!='*') b[i].x=(B[i]-'a'+1)*(B[i]-'a'+1)*(B[i]-'a'+1);
FFT(a),FFT(b);
for(int i=0;i<=lim;++i)
a[i]=a[i]*b[i];
FFT(a,-1);
for(int i=n-1,j=0;i<=m-1;++i,++j)
val[j]+=a[i].x;
for(int i=0;i<=lim;++i)
a[i]=b[i]=Complex(0,0);
for(int i=0;i<n;++i)
if(A[i]!='*') a[i].x=(A[i]-'a'+1)*(A[i]-'a'+1)*(A[i]-'a'+1);
for(int i=0;i<m;++i)
if(B[i]!='*') b[i].x=(B[i]-'a'+1);
FFT(a),FFT(b);
for(int i=0;i<=lim;++i)
a[i]=a[i]*b[i];
FFT(a,-1);
for(int i=n-1,j=0;i<=m-1;++i,++j)
val[j]+=a[i].x;
for(int i=0;i<=lim;++i)
a[i]=b[i]=Complex(0,0);
for(int i=0;i<n;++i)
if(A[i]!='*') a[i].x=(A[i]-'a'+1)*(A[i]-'a'+1);
for(int i=0;i<m;++i)
if(B[i]!='*') b[i].x=(B[i]-'a'+1)*(B[i]-'a'+1);
FFT(a),FFT(b);
for(int i=0;i<=lim;++i)
a[i]=a[i]*b[i];
FFT(a,-1);
for(int i=n-1,j=0;i<=m-1;++i,++j)
if(int((val[j]-2*a[i].x)/lim+0.5)==0) id[++ans]=j;
printf("%d\n",ans);
for(int i=1;i<=ans;++i)
printf("%d ",id[i]+1);
return 0;
}
