【bzoj4503】两个串 FFT

$FFT$套路题（然而我看错题了）

我们考虑化一下式子。

设当前比较的两个部分为$S[i....i+|T|-1]$和$T[0....|T|-1]$。

我们对串$T$中出现问号的位置全部赋值为$0$。

我们定义一个差异度$C[i]=sum_{j=0}^{|T|-1}T[j](S[i+j]-T[j])^2$

显然当$C[i]$为$0$时，$S[i....i+|T|-1]$和$T[0....|T|-1]$可以实现匹配。

我们把式子拆开分析，则有

$C[i]=sum_{j=0}{|T|-1}S[i+j]^2T[j]-2S[i+j]T[j]^2+T[j]^3$

然后我们将$T$串翻转一下，就会发现这个式子可以变成一个卷积的形式。

然后我们就可以用$FFT$去求出每一个$C[i]$，显然$T[i]^3$可以直接求。

完结撒花~

 1 #include<bits/stdc++.h>
 2 #define L long long
 3 #define MOD 998244353
 4 #define G 3
 5 #define M 1<<18
 6 using namespace std;
 7 
 8 L pow_mod(L x,L k){
 9     L ans=1;
10     for(;k;x=x*x%MOD,k>>=1)
11     if(k&1) ans=ans*x%MOD;
12     return ans;
13 }
14 
15 L a[M]={0},b[M]={0},aa[M]={0},bb[M]={0},ans[M]={0}; int n; 
16 
17 void change(L a[],int n){
18     for(int i=0,j=0;i<n-1;i++){
19         if(i<j) swap(a[i],a[j]);
20         int k=n>>1; 
21         while(j>=k) j-=k,k>>=1;
22         j+=k;
23     }
24 }
25 
26 void NTT(L a[],int n,int on){
27     change(a,n);
28     for(int h=2;h<=n;h<<=1){
29         L wn=pow_mod(G,(MOD-1)/h);
30         for(int j=0;j<n;j+=h){
31             L w=1;
32             for(int k=j;k<j+(h>>1);k++){
33                 L u=a[k],t=w*a[k+(h>>1)]%MOD;
34                 a[k]=(u+t)%MOD; 
35                 a[k+(h>>1)]=(u-t+MOD)%MOD;
36                 w=w*wn%MOD;
37             }
38         }
39     }
40     if(on==-1){
41         L inv=pow_mod(n,MOD-2);
42         for(int i=0;i<n;i++) a[i]=a[i]*inv%MOD;
43         reverse(a+1,a+n);
44     }
45 }
46 
47 char s[M]={0},c[M]={0};
48 int lens,lenc,len=1;
49 int main(){
50     scanf("%d%d",&lens,&lenc); 
51     scanf("%s%s",s,c);
52     lens=strlen(s); lenc=strlen(c);
53     while(len<lens+lenc) len<<=1;
54     reverse(c,c+lenc);
55     L sumb=0;
56     for(int i=0;i<lens;i++) a[i]=(s[i]-'a'+1),aa[i]=a[i]*a[i];
57     for(int i=0;i<lenc;i++) b[i]=(c[i]=='?'?0:c[i]-'a'+1),bb[i]=b[i]*b[i],sumb+=b[i]*b[i]*b[i];
58     sumb%=MOD;
59     NTT(a,len,1); NTT(aa,len,1);
60     NTT(b,len,1); NTT(bb,len,1);
61     for(int i=0;i<len;i++) ans[i]=(aa[i]*b[i]%MOD-2*a[i]*bb[i]%MOD+MOD)%MOD;
62     NTT(ans,len,-1);
63     int sum=0;
64     for(int i=lenc-1;i<lens;i++) 
65     if((ans[i]+sumb)%MOD==0) sum++;
66     cout<<sum<<endl;
67     for(int i=lenc-1;i<lens;i++)
68     if((ans[i]+sumb)%MOD==0) printf("%d
",i-lenc+1);
69 }

【bzoj4503】 两个串 FFT

【bzoj4503】两个串 FFT