题解 P4173 【残缺的字符串】
santongding
2018-03-03 00:52:52
好像没有题解。。。那我就说一说我的玄学做法
比较容易就能得出，如果将模板串翻转位置之后，不足的位置补零再与要匹配的串做fft，那么得出的多项式中F[ i ]是所有下标之和为i的两个字符的乘积，而由于模板串后边的位置被补零，所以能够找到n-m个F[i]表示所有匹配情况；（当然不必要真的补零，我大概觉着会好想一些吧。。。）
接下来考虑怎么判断每个情况是否合法，将模板串中26个字母都设为一个数，再将匹配串中所有字母设为倒数，如果有“*”号那么设为0，那么得出的每个表示匹配情况的值如果是个整数，就是合法的，如果不是就不合法；
当然这样很有可能有精度问题，所以得给每个字符一开始的值加一个数，似乎加个1000左右的数就可以，加个100以内的可能会被卡；
至于判断是否是整数时，实测1e-6也是可以过；
总之这个做法比较玄学，但唯一的好处是只需要做一次fft，跑得比较快
```cpp
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define random(a,b) (a+rand()%(b-a+1))
#define pi 3.141592653589793238460643383279
const int maxn=1048577;
int n,m;
int nn=1,tk=0;
int a[maxn],b[maxn],c[maxn];
double abs(double x)
{
if(x<0)return -x;
return x;
}
struct com
{
double r,i;
com(){
r=i=0.0;
}
com(double x,double y){
r=x,i=y;
}
com operator +(const com &o)const{
return com(r+o.r,i+o.i);
}
com operator -(const com &o)const{
return com(r-o.r,i-o.i);
}
com operator *(const com &o)const{
return com(r*o.r-i*o.i,r*o.i+i*o.r);
}
com operator /(const double &o)const{
return com(r/o,i/o);
}
}c1[maxn],c2[maxn], omega[maxn];
void read(register int *t,int len)
{
char s;
for(register int i=0;i<len;i++)
{
s=getchar();
while(!isdigit(s))s=getchar();
t[i]=s-'0';
}
}
void swap(com &x,com &y)
{
com z=x;
x=y;
y=z;
}
void FFT(com *p)
{
for(register int i=0,j=0; i<nn; i++)
{
if(i>j)swap(p[i],p[j]);
for(register int l=nn>>1; (j^=l)<l; l>>=1);
}
for(register int l=2;l<=nn;l<<=1)
{
int mid=l/2;
for(com *t=p;t!=p+nn;t+=l)
for(register int i=0;i<mid;i++)
{
com tp=omega[nn/l*i] * t[i+mid];
t[i+mid]=t[i]-tp;
t[i]=t[i]+ tp;
}
}
}
com f[maxn],g[maxn];
int suma=0,sumb=0;
char sb[maxn];
int ans[maxn];
int anstot=0;
int main()
{
scanf("%d%d",&m,&n);
scanf("%s",sb);
for(int i=0;i<m;i++)
{
if(sb[i]=='*')f[m-1-i].r=0.0,sumb++;
else f[m-1-i].r=(double)(sb[i]-'a'+1000);
}
scanf("%s",sb);
for(int i=0;i<n;i++)
{
if(sb[i]=='*')g[i].r=0.0;
else g[i].r=1.0/(double)(sb[i]-'a'+1000);
}
while(nn<m+n-1)nn<<=1;
for(register int i=0;i<nn;i++)omega[i]=com(std::cos(2.0*pi/(double)nn*(double)(i)),std::sin(2.0*pi/(double)nn*(double)i));
FFT(f);
FFT(g);
for(register int i=0;i<nn;i++)
{
omega[i].i*=-1;
f[i]=f[i]*g[i];
}
FFT(f);
for(register int i=0;i<nn;i++)
f[i].r/=(double)nn;
for(int i=m-1;i<n;i++)
{
int tmp=(int)(f[i].r+0.5);//四舍五入
if(abs(f[i].r-(double)tmp)<=1e-6)ans[++anstot]=i-m+2;
}
printf("%d\n",anstot);
for(int i=1;i<=anstot;i++)printf("%d ",ans[i]);
return 0;
}
```
正解好像得拆开证一波。。。感觉我这种做法很容易被卡啊orz
UPD：本来没开o2在洛谷被前边几个开了o2的碾压，遂开一波o2强行rk1,毕竟我fft只需要做一次，手残大常数也无所谓orz