【BZOJ4503】两个串（FFT）

题面

给定串(S),以及带通配符的串(T)，询问(T)在(S)中出现了几次。并且输出对应的位置。

(|S|,|T|<=10^5),字符集大小为(26)

题解

先来考虑没有通配符怎么匹配。~~别跟我说KMP！！~~

根据前面几个题目的套路，我们可以把每个字符分开来考虑，然后将(T)串反转，将有这个字符的位置变成(1)，然后(FFT)，就可以知道在这一段里面这个字符匹配上了多少个，然后把每个字符求个和，检查是否恰好匹配了(|T|)个。

通配符此时并不需要考虑。

时间复杂度(O(26nlogn))

当然，如果您真的这么写了，那么肯定(T)飞了。(FFT)自带巨大常数。对于字符集很小的时候上述方法是可行的，字符集很大的时候就不能这么做了。

所以我们考虑如何只做一遍(FFT)。（没有通配符的情况下）

每个字符当然不能动了，所以把他们对应成数字。如果匹配上了怎么办？那就是上下两个对应的数字相等，可以考虑作差。但是又发现作差可能会使得几个正数和几个负数相加变成(0)，所以考虑平方。

所以，我们定义每个位置的函数值(f(x)=sum_{i=1}^{|T|}(S[x+i-1]-T[i])^2)

将(T)串反转，平方项拆开之后，就变成了两个卷积+一个常数项的形式，直接(FFT)然后求和，检查最后的函数值是否为(0)就行了。

现在有了通配符，我们不妨令(a..z)对应的数字为(1..26)。通配符无论给它一个什么数字，它和上面的字符的差的平方一定不为(0)。

所以我们换种方法考虑，把通配符对应的数字设为(0)，但是这样差的平方不是(0)，所以我们就在上面那个式子后面乘上一个(T[i])的权值，如果此时是通配符就会乘(0)，从而也变成了(0)。这样一来，原来的式子就变成了(f(x)=sum_{i=1}^{|T|}(S[x+i-1]-T[i])^2T[i])

拆开后是两个卷积+一个常数项的形式，(FFT)即可。

时间复杂度(O(nlogn))

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
#define MAX 333333
const double Pi=acos(-1);
struct Complex{double a,b;}A1[MAX],B1[MAX],A2[MAX],B2[MAX],W[MAX],F[MAX];
Complex operator+(Complex a,Complex b){return (Complex){a.a+b.a,a.b+b.b};}
Complex operator-(Complex a,Complex b){return (Complex){a.a-b.a,a.b-b.b};}
Complex operator*(Complex a,Complex b){return (Complex){a.a*b.a-a.b*b.b,a.a*b.b+a.b*b.a};}
int n,m,r[MAX],N,Z;
int pos[MAX],ans,l;
char S[MAX],T[MAX];
void FFT(Complex *P,int opt)
{
	for(int i=1;i<N;++i)if(i<r[i])swap(P[i],P[r[i]]);
	for(int i=1;i<N;i<<=1)
		for(int p=i<<1,j=0;j<N;j+=p)
			for(int k=0;k<i;++k)
			{
				Complex w=(Complex){W[N/i*k].a,W[N/i*k].b*opt};
				Complex X=P[j+k],Y=w*P[j+k+i];
				P[j+k]=X+Y;P[i+j+k]=X-Y;
			}
	if(opt==-1)for(int i=0;i<N;++i)P[i].a/=N;
}
int main()
{
	scanf("%s",S);scanf("%s",T);
	n=strlen(S);m=strlen(T);
	for(N=1;N<=(n+m-2);N<<=1)++l;
	for(int i=0;i<N;++i)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
	for(int i=1;i<N;i<<=1)
		for(int k=0;k<i;++k)W[N/i*k]=(Complex){cos(k*Pi/i),sin(k*Pi/i)};
	for(int i=0;i<n;++i)A1[i].a=(S[i]-96)*(S[i]-96),A2[i].a=2*(S[i]-96);
	for(int i=0;i<m;++i)
	{
		int x=((T[m-i-1]=='?')?0:(T[m-i-1]-96));
		B1[i].a=x;B2[i].a=x*x;Z+=x*x*x;
	}
	FFT(A1,1);FFT(B1,1);FFT(A2,1);FFT(B2,1);
	for(int i=0;i<N;++i)
		F[i]=A1[i]*B1[i]-A2[i]*B2[i];
	FFT(F,-1);
	for(int i=m-1;i<n;++i)
		if((int)(F[i].a+0.5+Z)==0)pos[++ans]=i-m+1;
	printf("%d
",ans);
	for(int i=1;i<=ans;++i)printf("%d
",pos[i]);
	return 0;
}