wordpress 点击文章,上海seo网站优化,台州seo全网营销,产品网站免费模板下载地址题解#xff1a; 将字符串A、B中的a和b分别以1和-1表示#xff0c;对字符串B进行反转。 将A和B看成多项式#xff0c;求卷积#xff0c;这样的话从结果区间的[lenB−1,lenA)[lenB−1,lenA)中的每一个点的值valval#xff0c;(lenB−val)/2(lenB−val)/2代表当前位置的字串…题解 将字符串A、B中的a和b分别以1和-1表示对字符串B进行反转。 将A和B看成多项式求卷积这样的话从结果区间的[lenB−1,lenA)[lenB−1,lenA)[lenB-1,lenA)中的每一个点的值valvalval(lenB−val)/2(lenB−val)/2(lenB-val)/2代表当前位置的字串与B串的距离然后对字串进行字符串hash去重就是答案。 #include iostream
#include cstdio
#include cmath
#include algorithm
#include cstring
#include set
using namespace std;
double pi acos(-1.0);
struct complex{double re,im;complex(double r 0.0,double i 0.0):re(r),im(i){};complex operator(complex com){return complex(recom.re,imcom.im);}complex operator-(complex com){return complex(re-com.re,im-com.im);}complex operator*(complex com){return complex(re*com.re-im*com.im,re*com.imim*com.re);}
};
complex wn,wntmp;
void rader(complex arr[],int n){int num n-1;for(int i 0;i n;i){int tn n1;while(num num tn) num ^ tn,tn 1;num | tn;if(num i) swap(arr[i],arr[num]);}
}
void FFT(complex cs[],int n,int f){rader(cs,n);for(int s 1;s n;s 1){wn complex(cos(f*2*pi/(s*2)),sin(f*2*pi/(s*2)));for(int offset 0;offset n;offset s1){wntmp complex(1.0,0.0);for(int i 0;i s;i){complex u cs[offseti],v cs[offsetis]*wntmp;cs[offseti] u v;cs[offsetis] u - v;wntmp wntmp * wn;}}}if(f -1)for(int i 0;i n;i)cs[i].re / n;
}
int K;
const int maxn 600007;
char A[maxn],B[maxn];
complex csA[maxn],csB[maxn];
unsigned long long fac 9973;
unsigned long long pow(int x){unsigned long long ans 1,base fac;while(x){if(x 1)ans * base;base * base;x 1;}return ans;
}
int main(){int cas 0;while(cinK K ! -1){memset(csA,0,sizeof(csA)),memset(csB,0,sizeof(csB));cinAB;int lenA strlen(A),lenB strlen(B);for(int i 0;i lenB/2;i) swap(B[i],B[lenB-i-1]);int len 1;while(len lenA || len lenB) len 1;len 1;for(int i 0;i lenA;i) csA[i].re A[i] a?1:-1;FFT(csA,len,1);for(int i 0;i lenB;i) csB[i].re B[i] a?1:-1;FFT(csB,len,1);for(int i 0;i len;i) csA[i] csA[i]*csB[i];FFT(csA,len,-1);setunsigned long long st;unsigned long long hash 0,base pow(lenB-1);for(int i 0;i lenB;i) hash hash*fac (A[i] a);long long ans 0; for(int i lenB-1;i lenA;i){int dis (lenB - int(csA[i].re100000.5) 100000)/2;if(dis K) st.insert(hash),ans;hash (hash - base * (A[i-lenB1] a))*fac(A[i1] a);}printf(Case %d: %d\n,cas,st.size());}return 0;
}
