CF954I Yet Another String Matching Problem

|

写这题的时候潮子一直在边上潮,结果一遍就A了,看来以后要多让潮子潮潮我。

传送门

先假装证明一下贪心的正确性,如果一个位置两个串颜色不一样,那么我们迟早要有一个操作把这两种字符变成同一种。不然就要借助第三种颜色变两次,所以一定没有比这种贪心更优的方法。

然后对于每个位置属于$x\in [0,n-m]$,我只要知道它后面m个字符中有没有颜色p,q对应(即有一个位置i,$a_i=p,b_{i+x-1}=q$),就可以确定要不要把颜色p,q合并起来(如果p和q之前没有被合并的话,用并查集维护一下),进而也可以算出在x位置的答案。

那么我只要求出$[x,x+m-1]$中有没有颜色p,q的对应就好了。

这个可以用多项式乘法做,枚举p,q,将a中p出现的位置赋成1(多项式a),b中q出现的位置赋成1(多项式b),将多项式a翻转后和多项式b乘起来即可,这是FFT解决字符串匹配问题的套路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#define maxn 500000
using namespace std;
const double Pi=acos(-1.0);
struct complex{
double x,y;
complex (double xx=0,double yy=0){x=xx,y=yy;}
}a[maxn],b[maxn],c[maxn];
int fa[7],n,m,lim,r[maxn],e[maxn][6][6],l,ans;
char ch1[maxn],ch2[maxn];
complex operator + (complex a,complex b){return complex(a.x+b.x,a.y+b.y);}
complex operator - (complex a,complex b){return complex(a.x-b.x,a.y-b.y);}
complex operator * (complex a,complex b){return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
inline void FFT(complex *a,int inv){
for (int i=0; i<lim; i++)
if (i<r[i]) swap(a[i],a[r[i]]);
for (int i=1; i<lim; i<<=1){
complex wn(cos(Pi/i),inv*sin(Pi/i));
for (int j=0; j<lim; j+=(i<<1)){
complex w(1,0);
for (int k=0; k<i; k++,w=w*wn){
complex x=a[j+k],y=w*a[j+i+k];
a[j+k]=x+y; a[i+j+k]=x-y;
}
}
}
}
int find(int x){
if (fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
int main(){
scanf("%s",ch1); n=strlen(ch1);
scanf("%s",ch2); m=strlen(ch2);
lim=1; while (lim<=n+m) lim<<=1,l++;
for (int i=0; i<lim; i++)
r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
for (int p=0; p<6; p++)
for (int q=0; q<6; q++){
if (p==q) continue;
for (int i=0; i<lim; i++) a[i]=b[i]=complex(0,0);
for (int i=0; i<m; i++) a[m-1-i].x=(ch2[i]==p+'a');
for (int i=0; i<n; i++) b[i].x=(ch1[i]==q+'a');
FFT(a,1); FFT(b,1);
for (int i=0; i<=lim; i++) c[i]=a[i]*b[i];
FFT(c,-1);
// printf("\n%d %d\n",p,q);
for (int i=m-1; i<n; i++){
e[i-m+1][p][q]=(int)(c[i].x/lim+0.5);
// printf("%d ",e[i-m+1][p][q]);
}
}
for (int k=0; k<=n-m; k++){
for (int i=0; i<6; i++) fa[i]=i;
ans=0;
for (int p=0; p<6; p++)
for (int q=0; q<6; q++){
if (p==q) continue;
// printf("k:%d p:%d q:%d %d\n",k,p,q,e[k][p][q]);
if (!e[k][p][q]) continue;
int x=find(p),y=find(q);
if (x!=y) fa[x]=y,ans++;
}
// for (int i=0; i<6; i++)
// if (find(i)!=i) ans++;
printf("%d ",ans);
}
return 0;
}
,
载入天数...载入时分秒... 字数统计:57.6k