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解决字符串匹配问题的套路。

#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;
}