题意：给出两个由小写$a$到$f$组成的字符串$S$和$T$($|S| \geq |T|$)，给出变换$c1\,c2$表示将两个字符串中所有$c1$字符变为$c2$，求$S$的每一个长度为$T$的子串与$T$做变换使得两个字符串相等的最小变换次数。$1 \leq |T| \leq |S| \leq 1.25 \times 10^5$
弱化版：CF939D
PS：默认字符串开头是第$0$位
我们同样考虑通过CF939D的那种方法解决这个问题。考虑到这道题的字符集大小只有$6$，也就是说本质不同的边的条数只有$30$条。我们可以考虑枚举$S$中的字符$x$与$T$中的字符$y$的连边情况。将$T$反序后，将$S$中的字符$x$对应为$1$，T中的字符$y$也对应为$1$，其他的都对应为$0$。然后对这两个对应的数组做$FFT$，这样得到的结果的第$x$位如果不为$0$，意味着$S$的以第$x - |T| + 1$位为开头的子串中存在$x$到$y$的连边（如果不是很理解可以自己画图qwq）。然后对每一个$S$的子串开并查集维护就可以了。复杂度$O(30nlogn)$
#include<bits/stdc++.h>
#define eps 1e-2
#define ld long double
//This code is written by Itst
using namespace std;
inline int read(){
;
;
char c = getchar();
while(c != EOF && !isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(c != EOF && isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
;
char s1[MAXN] , s2[MAXN];
struct comp{
ld x , y;
comp(ld _x = , ld _y = ){
x = _x;
y = _y;
}
comp operator +(comp a){
return comp(x + a.x , y + a.y);
}
comp operator -(comp a){
return comp(x - a.x , y - a.y);
}
comp operator *(comp a){
return comp(x * a.x - y * a.y , x * a.y + y * a.x);
}
}A[MAXN] , B[MAXN];
);
] , ans[MAXN] , dir[MAXN] , need;
inline void FFT(comp* a , int type){
; i < need ; ++i)
if(i < dir[i])
swap(a[i] , a[dir[i]]);
; i < need ; i <<= ){
comp wn(cos(pi / i) , type * sin(pi / i));
; j < need ; j += i << ){
comp w( , );
; k < i ; ++k , w = w * wn){
comp x = a[j + k] , y = a[i + j + k] * w;
a[j + k] = x + y;
a[i + j + k] = x - y;
}
}
}
}
bool cmp(ld a , ld b){
return a - eps < b && a + eps > b;
}
int find(int dir , int x){
return fa[dir][x] == x ? x : (fa[dir][x] = find(dir , fa[dir][x]));
}
int main(){
#ifndef ONLINE_JUDGE
freopen("954I.in" , "r" , stdin);
//freopen("954I.out" , "w" , stdout);
#endif
scanf("%s%s" , s1 , s2);
int l1 = strlen(s1) , l2 = strlen(s2);
; i < (l2 >> ) ; ++i)
swap(s2[i] , s2[l2 - i - ]);
need = ;
)
need <<= ;
; i <= l1 - l2 ; ++i)
; j <= ; ++j)
fa[i][j] = j;
; i < need ; ++i)
dir[i] = (dir[i >> ] >> ) | (i & ? need >> : );
; i <= ; ++i)
; j <= ; ++j)
if(i != j){
; k < need ; ++k){
A[k].x = s1[k] == 'a' + i;
A[k].y = ;
}
; k < need ; ++k){
B[k].x = s2[k] == 'a' + j;
B[k].y = ;
}
FFT(A , );
FFT(B , );
; k < need ; ++k)
A[k] = A[k] * B[k];
FFT(A , -);
; k < l1 ; ++k)
))
, i + ) != find(k - l2 + , j + )){
fa[k - l2 + ][find(k - l2 + , i + )] = find(k - l2 + , j + );
++ans[k - l2 + ];
}
}
; i <= l1 - l2 ; ++i)
printf("%d " , ans[i]);
;
}