M_sea

洛谷4173 残缺的字符串
Luogu分析$\mathrm{FFT}$ 。令 * 为 $0$ ,a 为 $1$ ,.....定义 $dis(A...
扫描右侧二维码阅读全文
03
2019/04

洛谷4173 残缺的字符串

Luogu

分析

$\mathrm{FFT}$ 。

* 为 $0$ ,a 为 $1$ ,.....

定义 $dis(A,B)=\sum\limits_{i=0}^{n-1}(A_i-B_i)^2A_iB_i$ 。

显然,当且仅当 $dis(A,B)=0$ 时,$A=B$ 。

展开一下 $dis(A,B)=\sum\limits_{i=0}^{n-1}({A_i}^3Bi-2{A_i}^2{B_i}^2+A_i{B_i}^3)$ 。

如果将 $A$ 翻转的话,会发现后面是个卷积的形式。于是只要用 $\mathrm{FFT}$ 算一下,然后求出所有为 $0$ 的下标就行了。

另外,此题比较卡常。(可能只有我被卡了)

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1200000+10;

struct Complex {
    double x,y;
    Complex(double x_=0,double y_=0):x(x_),y(y_) { }
};
Complex operator +(Complex a,Complex b) { return Complex(a.x+b.x,a.y+b.y); }
Complex operator -(Complex a,Complex b) { return Complex(a.x-b.x,a.y-b.y); }
Complex operator *(Complex a,Complex b) { return Complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x); }

int r[N];

inline void FFT(Complex* a,int n,int op) {
    for (re int i=0;i<n;++i) if (i<r[i]) swap(a[i],a[r[i]]);
    for (re int i=1;i<n;i<<=1) {
        Complex rot(cos(M_PI/i),op*sin(M_PI/i));
        for (re int j=0;j<n;j+=(i<<1)) {
            Complex w(1,0);
            for (re int k=0;k<i;++k,w=w*rot) {
                Complex x=a[j+k],y=w*a[j+k+i];
                a[j+k]=x+y,a[j+k+i]=x-y;
            }
        }
    }
    if (op==-1) {
        for (re int i=0;i<n;++i) a[i].x/=n;
    }
}

char s1[N],s2[N];
int a[N],b[N];
Complex f[N],g[N],ans[N];
int sta[N],top;

int main() {
    int m=read(),n=read(); scanf("%s%s",s1,s2);
    for (re int i=0;i<m;++i) a[i]=(s1[m-i-1]=='*')?0:s1[m-i-1]-'a'+1;
    for (re int i=0;i<n;++i) b[i]=(s2[i]=='*')?0:s2[i]-'a'+1;

    int len=1,l=0;
    for (;len<n+n;len<<=1,++l);
    for (re int i=0;i<len;++i) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));

    for (re int i=0;i<m;++i) f[i]=Complex(a[i]*a[i]*a[i]);
    for (re int i=0;i<n;++i) g[i]=Complex(b[i]);
    FFT(f,len,1),FFT(g,len,1);
    for (re int i=0;i<len;++i) ans[i]=f[i]*g[i];

    for (re int i=0;i<m;++i) f[i]=Complex(a[i]*a[i]);
    for (re int i=m;i<len;++i) f[i]=Complex();
    for (re int i=0;i<n;++i) g[i]=Complex(b[i]*b[i]);
    for (re int i=n;i<len;++i) g[i]=Complex();
    FFT(f,len,1),FFT(g,len,1);
    for (re int i=0;i<len;++i) ans[i]=ans[i]-2*f[i]*g[i];

    for (re int i=0;i<m;++i) f[i]=Complex(a[i]);
    for (re int i=m;i<len;++i) f[i]=Complex();
    for (re int i=0;i<n;++i) g[i]=Complex(b[i]*b[i]*b[i]);
    for (re int i=n;i<len;++i) g[i]=Complex();
    FFT(f,len,1),FFT(g,len,1);
    for (re int i=0;i<len;++i) ans[i]=ans[i]+f[i]*g[i];

    FFT(ans,len,-1);
    for (re int i=m-1;i<n;++i)
        if (ans[i].x<0.5) sta[++top]=i-m+2;
    printf("%d\n",top);
    for (re int i=1;i<=top;++i) printf("%d ",sta[i]); puts("");
    return 0;
}
最后修改:2019 年 05 月 26 日 09 : 31 PM

发表评论