微信网站开发制作公司,鞋服外包加工网,小程序投票系统,网站设计要多少钱这题好神啊#xff0c;居然是fft#xff0c;表示一直在往数据结构上想。 把*当成0#xff0c;那么两个串可以匹配当且仅当$$\sum (a[i]-b[i])^2\times a[i]\times b[i]0$$ 我们可以把平方拆开#xff0c;然后就变成了几个乘积相加的形式#xff0c;那就大力翻转一个串然后… 这题好神啊居然是fft表示一直在往数据结构上想。 把*当成0那么两个串可以匹配当且仅当$$\sum (a[i]-b[i])^2\times a[i]\times b[i]0$$ 我们可以把平方拆开然后就变成了几个乘积相加的形式那就大力翻转一个串然后跑FFT。 因为最开始MLE了所以复制粘贴了好多东西。 1 #includeiostream2 #includecstring3 #includecstdio4 #includealgorithm5 #includecmath6 #define N 12000057 #define M 3000058 #define pi acos(-1)9 #define E complex10 using namespace std;11 struct complex12 {13 double x,y;14 complex(double _x,double _y){x_x;y_y;}15 complex(){;}16 friend complex operator * (const complex a,const complex b)17 {18 complex c;c.xa.x*b.x-a.y*b.y;c.ya.x*b.ya.y*b.x;return c;19 }20 friend complex operator / (complex a,double b)21 {22 return complex(a.x/b,a.y/b);23 }24 friend complex operator (complex a,complex b)25 {26 return complex(a.xb.x,a.yb.y);27 }28 friend complex operator - (complex a,complex b)29 {30 return complex(a.x-b.x,a.y-b.y);31 }32 };33 int R[N];int n;34 void fft(E *a,int f)35 {36 for(int i0;in;i)if(iR[i])swap(a[i],a[R[i]]);37 for(int i1;in;i1)38 {39 E wn(cos(pi/i),f*sin(pi/i));40 for(int j0;jn;j(i1))41 {42 E w(1,0);43 for(int k0;ki;k,ww*wn)44 {45 E xa[jk],yw*a[jki];46 a[jk]xy;a[jki]x-y;47 }48 }49 }50 if(f-1)for(int i0;in;i)a[i]a[i]/n;51 }52 int nn,mm;53 char s1[M],s2[M],s3[M];54 E a1[N],b1[N],c1[N];55 int ans[N];56 int st[M],top;57 int main()58 {59 scanf(%d%d,nn,mm);60 scanf(%s,s3);scanf(%s,s2);61 int l0;62 for(n1;n2*mm;n1)l;63 for(int i0;in;i)R[i](R[i1]1)|((i1)(l-1));64 for(int i0;inn;i)s1[i]s3[nn-i-1];65 for(int i0;imm;i)66 {67 int tmps2[i]-a1;double ptmp0.0;68 if(s2[i]*)p0;69 b1[i].xp;70 }71 for(int i0;inn;i)72 {73 int tmps1[i]-a1;double ptmp0.0;74 if(s1[i]*)p0;75 a1[i].xp*p*p;76 }77 fft(a1,1);fft(b1,1);78 for(int i0;in;i)c1[i]a1[i]*b1[i];79 for(int i0;in;i)a1[i].xa1[i].yb1[i].xb1[i].y0;80 81 for(int i0;imm;i)82 {83 int tmps2[i]-a1;double ptmp0.0;84 if(s2[i]*)p0;85 b1[i].xp*p;86 }87 for(int i0;inn;i)88 {89 int tmps1[i]-a1;double ptmp0.0;90 if(s1[i]*)p0;91 a1[i].xp*p;92 }93 fft(a1,1);fft(b1,1);94 for(int i0;in;i)c1[i]c1[i]-(a1[i]*b1[i]),c1[i]c1[i]-(a1[i]*b1[i]);95 for(int i0;in;i)a1[i].xa1[i].yb1[i].xb1[i].y0;96 97 for(int i0;imm;i)98 {99 int tmps2[i]-a1;double ptmp0.0;
100 if(s2[i]*)p0;
101 b1[i].xp*p*p;
102 }
103 for(int i0;inn;i)
104 {
105 int tmps1[i]-a1;double ptmp0.0;
106 if(s1[i]*)p0;
107 a1[i].xp;
108 }
109 fft(a1,1);fft(b1,1);
110 for(int i0;in;i)c1[i]c1[i](a1[i]*b1[i]);
111
112 fft(c1,-1);
113
114 for(int inn-1;imm;i)
115 {
116 if(fabs(c1[i].x)0.5)
117 {
118 st[top]i-nn2;
119 }
120 }
121 printf(%d\n,top);
122 for(int i1;itop;i)
123 {
124 if(i!top)printf(%d ,st[i]);
125 else printf(%d\n,st[i]);
126 }
127 return 0;
128 } 转载于:https://www.cnblogs.com/ezyzy/p/6511727.html
