题意：给出两个由小写$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$
弱化版：
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)$
1 #include2 #define eps 1e-2 3 #define ld long double 4 //This code is written by Itst 5 using namespace std; 6 7 inline int read(){ 8 int a = 0; 9 bool f = 0; 10 char c = getchar(); 11 while(c != EOF && !isdigit(c)){ 12 if(c == '-') 13 f = 1; 14 c = getchar(); 15 } 16 while(c != EOF && isdigit(c)){ 17 a = (a << 3) + (a << 1) + (c ^ '0'); 18 c = getchar(); 19 } 20 return f ? -a : a; 21 } 22 23 const int MAXN = 265000; 24 char s1[MAXN] , s2[MAXN]; 25 struct comp{ 26 ld x , y; 27 28 comp(ld _x = 0 , ld _y = 0){ 29 x = _x; 30 y = _y; 31 } 32 33 comp operator +(comp a){ 34 return comp(x + a.x , y + a.y); 35 } 36 37 comp operator -(comp a){ 38 return comp(x - a.x , y - a.y); 39 } 40 41 comp operator *(comp a){ 42 return comp(x * a.x - y * a.y , x * a.y + y * a.x); 43 } 44 }A[MAXN] , B[MAXN]; 45 const ld pi = acos(-1); 46 int fa[MAXN][7] , ans[MAXN] , dir[MAXN] , need; 47 48 inline void FFT(comp* a , int type){ 49 for(int i = 1 ; i < need ; ++i) 50 if(i < dir[i]) 51 swap(a[i] , a[dir[i]]); 52 for(int i = 1 ; i < need ; i <<= 1){ 53 comp wn(cos(pi / i) , type * sin(pi / i)); 54 for(int j = 0 ; j < need ; j += i << 1){ 55 comp w(1 , 0); 56 for(int k = 0 ; k < i ; ++k , w = w * wn){ 57 comp x = a[j + k] , y = a[i + j + k] * w; 58 a[j + k] = x + y; 59 a[i + j + k] = x - y; 60 } 61 } 62 } 63 } 64 65 bool cmp(ld a , ld b){ 66 return a - eps < b && a + eps > b; 67 } 68 69 int find(int dir , int x){ 70 return fa[dir][x] == x ? x : (fa[dir][x] = find(dir , fa[dir][x])); 71 } 72 73 int main(){ 74 #ifndef ONLINE_JUDGE 75 freopen("954I.in" , "r" , stdin); 76 //freopen("954I.out" , "w" , stdout); 77 #endif 78 scanf("%s%s" , s1 , s2); 79 int l1 = strlen(s1) , l2 = strlen(s2); 80 for(int i = 0 ; i < (l2 >> 1) ; ++i) 81 swap(s2[i] , s2[l2 - i - 1]); 82 need = 1; 83 while(need < l1 + l2 - 1) 84 need <<= 1; 85 for(int i = 0 ; i <= l1 - l2 ; ++i) 86 for(int j = 1 ; j <= 6 ; ++j) 87 fa[i][j] = j; 88 for(int i = 1 ; i < need ; ++i) 89 dir[i] = (dir[i >> 1] >> 1) | (i & 1 ? need >> 1 : 0); 90 for(int i = 0 ; i <= 5 ; ++i) 91 for(int j = 0 ; j <= 5 ; ++j) 92 if(i != j){ 93 for(int k = 0 ; k < need ; ++k){ 94 A[k].x = s1[k] == 'a' + i; 95 A[k].y = 0; 96 } 97 for(int k = 0 ; k < need ; ++k){ 98 B[k].x = s2[k] == 'a' + j; 99 B[k].y = 0;100 }101 FFT(A , 1);102 FFT(B , 1);103 for(int k = 0 ; k < need ; ++k)104 A[k] = A[k] * B[k];105 FFT(A , -1);106 for(int k = l2 - 1 ; k < l1 ; ++k)107 if(!cmp(A[k].x , 0))108 if(find(k - l2 + 1 , i + 1) != find(k - l2 + 1 , j + 1)){109 fa[k - l2 + 1][find(k - l2 + 1 , i + 1)] = find(k - l2 + 1 , j + 1);110 ++ans[k - l2 + 1];111 }112 }113 for(int i = 0 ; i <= l1 - l2 ; ++i)114 printf("%d " , ans[i]);115 return 0;116 }