Vexoben
Jun 3, 2018
题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=4259
(刷新以获取数学公式)
题意
给定带通配符的两串和，求在中的出现位置。
题解
下面认为的下标范围是，的下标范围是
通配符的出现使kmp失去了效果。在不考虑通配符的情况下，用另一种方式思考字符串匹配。
，那么，在位置能匹配，当且仅当:
下标差为定值不能直接用FFT计算卷积，翻转使和变为定值。
令,则：
三部分计算完成后相加即可，则匹配。
那么考虑通配符呢？
如果是通配符，令，同理，那么只需即可
由于翻转的原因，如果，实际上是在的位置匹配。原题要求下标范围从1开始，那么再加1即可。
#include<bits/stdc++.h>
using namespace std;
const int N=(1<<20)+10;
const double pi=acos(-1.0);
char s[N],t[N];
int n,m,cnt,rev[N];
struct cp {
double x,y;
cp (double a,double b) {x=a,y=b;}
cp (){}
cp operator + (cp t) {return cp(x+t.x,y+t.y);}
cp operator - (cp t) {return cp(x-t.x,y-t.y);}
cp operator * (cp t) {return cp(x*t.x-y*t.y,x*t.y+y*t.x);}
}a[N],b[N],c[N],d[N],ans[N];
void FFT(cp *a,int limit,int type) {
for (int i=0;i<=limit;i++) if (i<rev[i]) swap(a[i],a[rev[i]]);
for (int len=2;len<=limit;len<<=1) {
int mid=len>>1;
cp wn(cos(2*pi/len),type*sin(2*pi/len));
for (int i=0;i<limit;i+=len) {
cp w(1,0);
for (int j=i;j<i+mid;j++) {
cp x=a[j],y=w*a[j+mid];
a[j]=x+y; a[j+mid]=x-y; w=w*wn;
}
}
}
if (type==-1) for (int i=0;i<=limit;i++) a[i].x/=limit;
}
void conv(cp *a,cp *b,int limit,int link) {
FFT(a,limit,1); FFT(b,limit,1);
for (int i=0;i<=limit;i++) a[i]=a[i]*b[i];
for (int i=0;i<=limit;i++) ans[i].x+=a[i].x*link,ans[i].y+=a[i].y*link;
}
int main() {
scanf("%d%d",&n,&m); n--; m--;
scanf("%s%s",t,s);
int limit=1,l=0;
while (limit<=n+m) l++,limit<<=1;
for (int i=0;i<=limit;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<l-1);
for (int i=0;i<=m;i++) a[i].x=(s[i]=='*')?0:s[i]-'a'+1;
for (int i=0;i<=n;i++) b[n-i].x=(t[i]=='*')?0:t[i]-'a'+1;
for (int i=0;i<=limit;i++) c[i]=a[i]*a[i]*a[i],d[i]=b[i];
conv(c,d,limit,1);
for (int i=0;i<=limit;i++) c[i]=a[i]*a[i],d[i]=b[i]*b[i];
conv(c,d,limit,-2);
for (int i=0;i<=limit;i++) c[i]=a[i],d[i]=b[i]*b[i]*b[i];
conv(c,d,limit,1);
FFT(ans,limit,-1);
for (int i=n;i<=m;i++) if (!(int)(ans[i].x+0.5)) cnt++;
printf("%d\n",cnt);
for (int i=n;i<=m;i++) if (!(int)(ans[i].x+0.5)) printf("%d ",i-n+1);
return 0;
}