海外网站服务器网址,wordpress+判断手机,桥西区附近网站建设价格,高质量的猎建筑人才传送门 题意#xff1a;给出两个由小写$a$到$f$组成的字符串$S$和$T$($|S| \geq |T|$)#xff0c;给出变换$c1\,c2$表示将两个字符串中所有$c1$字符变为$c2$#xff0c;求$S$的每一个长度为$T$的子串与$T$做变换使得两个字符串相等的最小变换次数。$1 \leq |T| \leq |S| \le…传送门 题意给出两个由小写$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)$ 1 #includebits/stdc.h2 #define eps 1e-23 #define ld long double4 //This code is written by Itst5 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_JUDGE75 freopen(954I.in , r , stdin);76 //freopen(954I.out , w , stdout);77 #endif78 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 } 转载于:https://www.cnblogs.com/Itst/p/10040546.html
