BZOJ4503 两个串 多项式 FFT

时间：2023-03-08 20:28:25

题目传送门 - BZOJ4503

题意概括

　　给定两个字符串S和T，回答T在S中出现了几次，在哪些位置出现。注意T中可能有?字符，可以匹配任何字符。

题解

　　首先，假装你已经知道了这是一道$FFT$题。

　　考虑怎样$FFT$。

　　字符串匹配的时候，对于匹配成功的对应字母的编号(比如分别是$i$和$j$)，满足了$i-j$都相同。但是我们需要的是$i+j$都相等。

　　于是我们用$FFT$的经典套路，翻转$T$串。

　　我们构造一个卷积：

　　$$\sum_{i=0}^{n}\sum_{j=0}^{m}(S_{i}-T_{j})^{2}S_{i}T_{j}$$

　　把他表示成这个形式：

　　$$h_i=\sum_{j=0}^j (S_{j}-T_{i-j})^{2}S_{j}T_{i-j}$$

　　其中对应的字符$c$如果为'?'值为$0$，否则为$c-'a'+1$。

　　这样的话，如果$h_i=0$的话那么就可以第$i$位开始匹配。

　　那么我们考虑求解这个式子。

　　我们只要展开一下：

　　$(S_i-T_j)^{2}S_{i}T_{j}\ = \ s_{i}^{3}t_{j}-2s_{i}^{2}t_{j}^{2}+s_{i}t_{j}^{3}$

　　然后变成了三组卷积，一坨$FFT$即可。

　　$Time：9000^+ MS$

　　震惊！

　　本题还有更优秀的解法。

　　对于没有问号的，我们$KMP$解决。

　　对于有问好的，暴搜解决。

　　复杂度极其优越。

　　$Time：100^- MS$

代码

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <cstdlib>

#include <vector>

using namespace std;

const int N=1<<18;

const double PI=acos(-1.0);

struct C{

	double r,i;

	C(){r=i=0;}

	C(double a,double b){r=a,i=b;}

	C operator + (C a){return C(r+a.r,i+a.i);}

	C operator - (C a){return C(r-a.r,i-a.i);}

	C operator * (C a){return C(r*a.r-i*a.i,r*a.i+i*a.r);}

}a[N],b[N],a1[N],b1[N],a2[N],b2[N],a3[N],b3[N],w[N];

int A,B,n,L,res[N],R[N];

double tot[N];

vector <int> ans;

char s[N],t[N];

void FFT (C a[N],int n){

	for (int i=0;i<n;i++)

		if (i<R[i])

			swap(a[i],a[R[i]]);

	for (int d=1,t=n>>1;d<n;d<<=1,t>>=1)

		for (int i=0;i<n;i+=(d<<1))

			for (int j=0;j<d;j++){

				C tmp=w[t*j]*a[i+j+d];

				a[i+j+d]=a[i+j]-tmp;

				a[i+j]=a[i+j]+tmp;

			}

}

int main(){

	scanf("%s%s",s,t);

	A=strlen(s),B=strlen(t);

	for (int i=0;i<B/2;i++)

		swap(t[i],t[B-i-1]);

	// (s-t)(s-t)st

	//=ssst-2sstt+sttt

	for (int i=0;i<n;i++)

		a[i]=b[i]=C(0,0);

	for (int i=0;i<A;i++)

		a[i].r=s[i]-'a'+1;

	for (int i=0;i<B;i++)

		b[i].r=t[i]=='?'?0:(t[i]-'a'+1);

	for (n=1,L=0;n<=A+B;n<<=1,L++);

	for (int i=0;i<n;i++){

		R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));

		w[i]=C(cos(2*i*PI/n),sin(2*i*PI/n));

		a1[i]=a[i]*a[i]*a[i];

		b1[i]=b[i];

		a2[i]=a[i]*a[i];

		b2[i]=b[i]*b[i];

		a3[i]=a[i];

		b3[i]=b[i]*b[i]*b[i];

	}

	FFT(a1,n),FFT(b1,n),FFT(a2,n),FFT(b2,n),FFT(a3,n),FFT(b3,n);

	for (int i=0;i<n;i++){

		a1[i]=a1[i]*b1[i];

		a2[i]=a2[i]*b2[i];

		a3[i]=a3[i]*b3[i];

		w[i].i*=-1.0;

	}

	FFT(a1,n),FFT(a2,n),FFT(a3,n);

	for (int i=0;i<n;i++)

		tot[i]=a1[i].r-2.0*a2[i].r+a3[i].r;

	for (int i=0;i<n;i++)

		res[i]=int(tot[i]+0.5);

	ans.clear();

	for (int i=B-1;i<A;i++)

		if (!res[i])

			ans.push_back(i-B+1);

	printf("%d\n",ans.size());

	for (vector <int>::iterator i=ans.begin();i!=ans.end();i++)

		printf("%d\n",*i);

	return 0;

}

　　

相关文章