分析
我们先考虑暴力如何计算
对于S的子串SS，如果它有位置i使得SS[i] != T[i]那么我们就将两个字符之间用并查集连边
最后答案很明显就是并查集中所有边的个数
于是我们可以发现对于S[i] != T[j]衣服那个会在S的第i-j个子串连边
我们通过观察可以发现i - j = i - (m - j) +m
这是一个卷积的形式
于是我们枚举S和T中考虑的是那种字符然后卷积判断连边关系
最后进行之前说的并查集即可
代码
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<cctype> #include<cmath> #include<cstdlib> #include<queue> #include<ctime> #include<vector> #include<set> #include<map> #include<stack>
using namespace std; const int mod = 998244353; const int g = 3; int fa[130000][6]; char s[130000],ot[130000],t[130000]; int n,m,r[460000],len,N,a[460000],b[460000],G,ans[460000]; inline int pw(int x,int p){ int res=1; while(p){ if(p&1)res=1ll*res*x%mod; x=1ll*x*x%mod; p>>=1; } return res; } inline void ntt(int a[],int f){ register int i,j,k; int now; for(i=0;i<n;++i) if(i<r[i])swap(a[i],a[r[i]]); for(i=1;i<n;i<<=1){ if(f==1)now=g; else now=G; int wn=pw(now,(mod-1)/(i<<1)); for(j=0;j<n;j+=(i<<1)){ int w=1,x,y; for(k=0;k<i;++k,w=1ll*w*wn%mod){ x=a[j+k],y=1ll*a[i+j+k]*w%mod; a[j+k]=(x+y)%mod,a[i+j+k]=(x+mod-y)%mod; } } } } inline int sf(int wh,int x){return fa[wh][x]==x?x:fa[wh][x]=sf(wh,fa[wh][x]);} signed main(){ register int i,j,k; int on,om; G=pw(g,mod-2); scanf("%s",s); scanf("%s",ot); n=strlen(s),m=strlen(ot); for(i=0;i<m;++i)t[i]=ot[m-i-1]; n--,m--; on=n,om=m; m+=n; for(n=1;n<=m;n<<=1)len++; for(i=0;i<n;++i)r[i]=((r[i>>1]>>1)|((i&1)<<(len-1))); for(i=om;i<=on;++i) for(j=0;j<6;++j)fa[i-om][j]=j; for(i=0;i<6;++i) for(j=0;j<6;++j){ if(i==j)continue; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); for(k=0;k<=on;++k)a[k]=((s[k]-'a')==i); for(k=0;k<=om;++k)b[k]=((t[k]-'a')==j); ntt(a,1),ntt(b,1); for(k=0;k<n;k++)a[k]=1ll*a[k]*b[k]%mod; ntt(a,-1); int inv=pw(n,mod-2); for(k=0;k<n;++k)a[k]=1ll*a[k]*inv%mod; for(k=om;k<=on;++k)if(a[k]){ int x=sf(k-om,i),y=sf(k-om,j); if(x==y)continue; ans[k-om]++; fa[k-om][x]=y; } } for(i=om;i<=on;++i)printf("%d ",ans[i-om]); return 0; }