[CF528D]Fuzzy Search

字符串 FFT/NTT

---

题面

给定原串$S$和匹配串$T$，允许错开不超过$k$位匹配（即$T$中第$i$位字符可以与$S$中$[i-k,i+k]$中的相同字符匹配）。问$|T|$在$|S|$中出现次数。
字符集大小为$4$。

• $|S|,|T|,k\leq2*10^5$

解析

在字符串问题上，都有一个通往卷积的套路：把某个字符串翻转。
这样可以使得两个字符串中，当前对应的字符坐标和均为$|S|+|T|$，满足卷积形式。
对每个字符串分开考虑，设两个多项式$A(x),B(x)$：(其中$char$表示当前枚举的字符）

$$A(x)=\sum_{i=0}^{|S|-1}(\exists char\in[i-k,i+k])x^i$$
$$B(x)=\sum_{i=0}^{|T|-1}(char==T[x])x^i$$
两个多项式卷一下，就是这种字符在$|S|$中第$i$个位置上的匹配数。
最后，如果有位置$4$个字符匹配数之和达到$|T|$，就说明形成了一种匹配方案。

其实这个玩意儿不太好理解。
设$A(x)$中第$i$位为$1$，$B(x)$中第$j$位为$1$，则两项相乘将贡献答案，放在$i+m-j+1$位。
同样放在这一位的答案，只有可能是$i++$且$j--$形成的。
而这样的过程对应的是串的匹配过程（翻转后）。

还有有人跟我说形成方案的位数（即$i+m-j+1$）小于$|S|$。。。我不能理解。。。

注意字符串起点位置必须是$0$！！！

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define cp complex
#define db double 
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=8e5+100;
const db pi=acos(-1);
int n,m,k,l,r[N],lim=1,ans[N/4],Ans;
char s1[N/4],s2[N/4],id[4]={'A','C','G','T'};
struct cp
{
  db x,y;
  il cp(){x=y=0;}
  il cp(re db xx,re db yy){x=xx,y=yy;}
}a[N],b[N];
il cp operator + (re cp a,re cp b){return cp(a.x+b.x,a.y+b.y);}
il cp operator - (re cp a,re cp b){return cp(a.x-b.x,a.y-b.y);}
il cp operator * (re cp a,re cp b){return cp(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
il void FFT(re cp *A,re int tp)
{
  fp(i,1,lim-1) if(i<r[i]) swap(A[i],A[r[i]]);
  for(re int mid=1;mid<lim;mid<<=1)
    {
       re cp W(cos(pi/mid),tp*sin(pi/mid));
       for(re int R=mid<<1,j=0;j<lim;j+=R)
       {
         re cp w(1,0);
         for(re int k=0;k<mid;++k,w=w*W)
         {
           re cp x=A[j+k],y=w*A[j+mid+k];
           A[j+k]=x+y;A[j+mid+k]=x-y;
         }
       }
    }
}
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
int main()
{
  n=gi();m=gi();k=gi();
  scanf("%s",s1);scanf("%s",s2);reverse(s2,s2+m);
  while(lim<=n+m) lim<<=1,++l;
  fp(i,1,lim-1) r[i]=(r[i>>1]>>1)|((i&1)<<l-1);
  fp(o,0,3)
  {
    fp(i,0,lim-1) a[i].x=a[i].y=b[i].x=b[i].y=0;
    re int pos=-1e9;
    fp(i,0,n-1)
    {
      if(s1[i]==id[o]) pos=i;
      if(pos>=i-k) a[i].x=1;
    }
    pos=1e9;
    fq(i,n-1,0)
    {
      if(s1[i]==id[o]) pos=i;
      if(pos<=i+k) a[i].x=1;
    }
    fp(i,0,m-1) if(s2[i]==id[o]) b[i].x=1;
    FFT(a,1);FFT(b,1);
    fp(i,0,lim-1) a[i]=a[i]*b[i];
    FFT(a,-1);
    fp(i,0,lim-1) ans[i]+=(int)(a[i].x/lim+0.5);
  }
  fp(i,0,lim-1) if(ans[i]==m) ++Ans;
  printf("%d\n",Ans);
  return 0;
}