Codeforces 954I Yet Another String Matching Problem

题意

给定两个字符串$S$和$T$($|T| \leqslant |S|$),询问$S$的$|S|-|T|+1$个长度为$|T|$的子串与$T$这个串的距离。两个串的距离定义为,要使得两个串变为完全相同,每次可以把两个串中的某一个字符全部改为另一个字符的最小操作次数。
$|T| \leqslant |S| \leqslant 125000$,字符集大小为$6$。

题解

对于两个串的距离,我们其实只需要判断对应位置上是否相等,如果不相等的话,就在并查集上连边就可以了。最后看并查集上有几个联通块即可。然后……暴力就一不小心过了这道题……
当然这里要讲的不是暴力啦。其实要想快速判断对应位置上是否相等,有一个更快的方法,我们可以把$T$串倒过来,再对于每一种字母的对应情况,都做一遍FFT就可以了。最后再在并查集上连边判断即可。
时间复杂度$O(36 \times n\log n)$。不得不吐槽一下,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
73
74
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=1e9;
const long double eps=1e-9;
const double Pi=acos(-1.0);
const int maxn=125000+10;
char a[maxn],b[maxn];
struct Complex{
double re,im;
}A[maxn<<2],B[maxn<<2];
int ans[maxn<<2][6][6],r[maxn<<2],fa[6];
int N;
inline Complex operator + (const Complex &lhs,const Complex &rhs){
return (Complex){lhs.re+rhs.re,lhs.im+rhs.im};
}
inline Complex operator - (const Complex &lhs,const Complex &rhs){
return (Complex){lhs.re-rhs.re,lhs.im-rhs.im};
}
inline Complex operator * (const Complex &lhs,const Complex &rhs){
return (Complex){lhs.re*rhs.re-lhs.im*rhs.im,lhs.re*rhs.im+lhs.im*rhs.re};
}
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
int find(int x){
return fa[x]==x ? x : fa[x]=find(fa[x]);
}
inline void FFT(Complex P[],int opt){
int i,j,k;
for(i=0;i<N;i++)if(i<r[i])swap(P[i],P[r[i]]);
for(i=2;i<=N;i<<=1){
int p=i/2;
Complex Wi=(Complex){cos(2*Pi/i),opt*sin(2*Pi/i)};
for(j=0;j<N;j+=i){
Complex x=(Complex){1,0};
for(k=0;k<p;k++,x=x*Wi){
Complex u=P[j+k],v=x*P[j+k+p];
P[j+k]=u+v;P[j+k+p]=u-v;
}
}
}
}
int main(){
int i,j,k,m,n;
#ifndef ONLINE_JUDGE
freopen("I.in","r",stdin);
freopen("I.out","w",stdout);
#endif
scanf("%s",a);scanf("%s",b);
n=strlen(a),m=strlen(b);
int tot=n+m,cnt=0;
for(N=1;N<=tot;N<<=1)cnt++;
for(i=0;i<N;i++)r[i]=r[i>>1]>>1 | ((i & 1)*(1<<(cnt-1)));
for(i=0;i<=5;i++)
for(j=0;j<=5;j++){
memset(A,0,sizeof(A));memset(B,0,sizeof(B));
for(k=0;k<n;k++)if(a[k]=='a'+i)A[k].re=1;
for(k=0;k<m;k++)if(b[m-k-1]=='a'+j)B[k].re=1;
FFT(A,1),FFT(B,1);
for(k=0;k<N;k++)A[k]=A[k]*B[k];
FFT(A,-1);
for(k=0;k<N;k++)ans[k][i][j]=(int)(A[k].re/N+0.5);
}
for(i=m-1;i<n;i++){
for(j=0;j<=5;j++)fa[j]=j;
for(j=0;j<=5;j++)
for(k=j+1;k<=5;k++)
if(ans[i][j][k] || ans[i][k][j]){
int u=find(j),v=find(k);
if(u==v)continue;
fa[u]=v;
}
int res=0;
for(j=0;j<=5;j++)if(fa[j]!=j)res++;
printf("%d%c",res,i==n-1?'\n':' ');
}
return 0;
}