Fuzzy Search

给你文本串 S 和模式串 T，求 S 的每个位置是否能模糊匹配上 T。

这里的模糊匹配指的是把 T 放到 S 相应位置上之后，T 中每个字符所在位置附近 k 个之内的位置上的 S 的字符至少有一个与之相同。

1 ≤ |T| ≤ |S| ≤ 200 000, 0 ≤ k ≤ 200 000。字符串是基因序列。

题解

由于字符集很小，所以对每种字符分别处理。

对 T 每个位置赋值为它是否等于这个字符。对 S 的每个位置前后找找有没有这种字符即可。

然后卷积看看匹配了多少个位置。每种字符的匹配位置数加起来等于 T 的长度的话，匹配就成功了。

时间复杂度 \(O(n \log n)\)。

struct node {LD x,y;};

IN node operator+(CO node&a,CO node&b){

	return (node){a.x+b.x,a.y+b.y};

}

IN node operator-(CO node&a,CO node&b){

	return (node){a.x-b.x,a.y-b.y};

}

IN node operator*(CO node&a,CO node&b){

	return (node){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};

}

IN node operator/(CO node&a,LD k){

	return (node){a.x/k,a.y/k};

}

CO int N=524288;

char s[N],t[N];

int cnt[100];

node sa[N],sg[N],sc[N],st[N];

node ta[N],tg[N],tc[N],tt[N];

node res[N];

bool ans[N];

CO LD pi=acos(-1),eps=1e-6;

int rev[N];

node omg[N];

void FFT(node a[],int lim){

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

		if(i<rev[i]) swap(a[i],a[rev[i]]);

	for(int i=1;i<lim;i<<=1)

		for(int j=0;j<lim;j+=i<<1)

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

				node t=omg[lim/(i<<1)*k]*a[j+i+k];

				a[j+i+k]=a[j+k]-t,a[j+k]=a[j+k]+t;

			}

}

int main(){

	int n=read<int>(),m=read<int>(),k=read<int>();

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

	reverse(t,t+m);

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

		if(t[i]=='A') ta[i]=(node){1,0};

		else if(t[i]=='G') tg[i]=(node){1,0};

		else if(t[i]=='C') tc[i]=(node){1,0};

		else tt[i]=(node){1,0};

	}

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

		++cnt[s[i]];

		if(cnt['A']) sa[i]=(node){1,0};

		if(cnt['G']) sg[i]=(node){1,0};

		if(cnt['C']) sc[i]=(node){1,0};

		if(cnt['T']) st[i]=(node){1,0};

		if(i>=k) --cnt[s[i-k]];

	}

	memset(cnt,0,sizeof cnt);

	for(int i=n-1;i>=0;--i){

		++cnt[s[i]];

		if(cnt['A']) sa[i]=(node){1,0};

		if(cnt['G']) sg[i]=(node){1,0};

		if(cnt['C']) sc[i]=(node){1,0};

		if(cnt['T']) st[i]=(node){1,0};

		if(i+k<=n-1) --cnt[s[i+k]];

	}

	memset(cnt,0,sizeof cnt);

	for(int i=0;i<m;++i) ++cnt[t[i]];

	fill(ans+m-1,ans+n,1);

	int len=ceil(log2(n)),lim=1<<len;

	for(int i=0;i<lim;++i) rev[i]=rev[i>>1]>>1|(i&1)<<(len-1);

	for(int i=0;i<lim;++i) omg[i]=(node){cos(i*2*pi/lim),sin(i*2*pi/lim)};

	FFT(sa,lim),FFT(ta,lim);

	for(int i=0;i<lim;++i) res[i]=sa[i]*ta[i];

	for(int i=0;i<lim;++i) omg[i].y=-omg[i].y;

	FFT(res,lim);

	for(int i=0;i<lim;++i) res[i]=res[i]/lim;

	for(int i=0;i<lim;++i) omg[i].y=-omg[i].y;

	for(int i=m-1;i<n;++i)

		if(fabs(res[i].x-cnt['A'])>eps) ans[i]=0;

	FFT(sg,lim),FFT(tg,lim);

	for(int i=0;i<lim;++i) res[i]=sg[i]*tg[i];

	for(int i=0;i<lim;++i) omg[i].y=-omg[i].y;

	FFT(res,lim);

	for(int i=0;i<lim;++i) res[i]=res[i]/lim;

	for(int i=0;i<lim;++i) omg[i].y=-omg[i].y;

	for(int i=m-1;i<n;++i)

		if(fabs(res[i].x-cnt['G'])>eps) ans[i]=0;

	FFT(sc,lim),FFT(tc,lim);

	for(int i=0;i<lim;++i) res[i]=sc[i]*tc[i];

	for(int i=0;i<lim;++i) omg[i].y=-omg[i].y;

	FFT(res,lim);

	for(int i=0;i<lim;++i) res[i]=res[i]/lim;

	for(int i=0;i<lim;++i) omg[i].y=-omg[i].y;

	for(int i=m-1;i<n;++i)

		if(fabs(res[i].x-cnt['C'])>eps) ans[i]=0;

	FFT(st,lim),FFT(tt,lim);

	for(int i=0;i<lim;++i) res[i]=st[i]*tt[i];

	for(int i=0;i<lim;++i) omg[i].y=-omg[i].y;

	FFT(res,lim);

	for(int i=0;i<lim;++i) res[i]=res[i]/lim;

	for(int i=0;i<lim;++i) omg[i].y=-omg[i].y;

	for(int i=m-1;i<n;++i)

		if(fabs(res[i].x-cnt['T'])>eps) ans[i]=0;

	int sum=0;

	for(int i=m-1;i<n;++i) sum+=ans[i];

	printf("%d\n",sum);

	return 0;

}

残缺的字符串

很久很久以前，在你刚刚学习字符串匹配的时候，有两个仅包含小写字母的字符串A和B，其中A串长度为m，B串长度为n。可当你现在再次碰到这两个串时，这两个串已经老化了，每个串都有不同程度的残缺。

你想对这两个串重新进行匹配，其中A为模板串，那么现在问题来了，请回答，对于B的每一个位置i，从这个位置开始连续m个字符形成的子串是否可能与A串完全匹配?

1<=m<=n<=300000

两个串均仅由小写字母和*号组成，其中*号表示相应位置已经残缺。

题解

这题跟上面那道几乎一样，只不过模糊匹配的方式更改了而已。

令通配符的位置的值为0，构造

ans_i=0时匹配成功。

这破题还是权限题。