周口网站建设专家,网站制作及管理教程,培训网站排名,设置字体颜色的网站正题
题目链接:https://www.luogu.com.cn/problem/P4173 题目大意
给出两个字符串S,TS,TS,T#xff0c;其中包含小写字母和一些???#xff0c;???可以匹配任何字符。
求有多少个ppp使得T0∼∣t∣−1Sp∼p∣t∣−1T_{0\sim |t|-1}S_{p\sim p|t|-1}T0∼∣t∣−1Sp∼…正题
题目链接:https://www.luogu.com.cn/problem/P4173 题目大意
给出两个字符串S,TS,TS,T其中包含小写字母和一些??????可以匹配任何字符。
求有多少个ppp使得T0∼∣t∣−1Sp∼p∣t∣−1T_{0\sim |t|-1}S_{p\sim p|t|-1}T0∼∣t∣−1Sp∼p∣t∣−1 解题思路
如果不考虑???我们可以用做差法来匹配两个字符构造匹配函数 f(x)∑i0m(Ti−Sxi)2f(x)\sum_{i0}^{m}(T_i-S_{xi})^2f(x)i0∑m(Ti−Sxi)2 这样若f(x)0f(x)0f(x)0证明它们在位置xxx处匹配。
但是现在有???也就是要跳过有???的位置定义???的值为000然后改一下匹配函数f(x)∑i0m(Ti−Sxi)2TiSxif(x)\sum_{i0}^{m}(T_i-S_{xi})^2T_iS_{xi}f(x)i0∑m(Ti−Sxi)2TiSxi
展开二次项f(x)∑i0mTi3Sxi−2Ti2Sxi2TiSxi3f(x)\sum_{i0}^{m}T_i^3S_{xi}-2T_{i}^2S_{xi}^2T_iS_{xi}^3f(x)i0∑mTi3Sxi−2Ti2Sxi2TiSxi3 把TTT反过来就是∑i0mTm−i−13Sxi−2Tm−i−12Sxi2Tm−i−1Sxi3\sum_{i0}^{m}T_{m-i-1}^3S_{xi}-2T_{m-i-1}^2S_{xi}^2T_{m-i-1}S_{xi}^3∑i0mTm−i−13Sxi−2Tm−i−12Sxi2Tm−i−1Sxi3
然后有三个式子卷积之后加起来就好了。
常数极大开-O2\text{-O2}-O2才能过。时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
#includecmath
#includequeue
#define int long long
using namespace std;
const int N1e62e5;
const double Piacos(-1);
struct complex{double x,y;complex(double xx0,double yy0){xxx;yyy;return;}
};
complex operator(complex a,complex b)
{return complex(a.xb.x,a.yb.y);}
complex operator-(complex a,complex b)
{return complex(a.x-b.x,a.y-b.y);}
complex operator*(complex a,complex b)
{return complex(a.x*b.x-a.y*b.y,a.x*b.ya.y*b.x);}
struct poly{complex a[N];
}F[3],G[3];
int n,m,r[N],k;
char s[N],t[N];
queueint q;
void FFT(complex *f,int op,int n){for(int i0;in;i)if(ir[i])swap(f[i],f[r[i]]);for(int p2;pn;p1){int lenp1;complex tmp(cos(Pi/len),sin(Pi/len)*op);for(int k0;kn;kp){complex buf(1,0);for(int ik;iklen;i){complex ttbuf*f[ilen];f[ilen]f[i]-tt;f[i]f[i]tt;bufbuf*tmp;}}}if(op-1)for(int i0;in;i)f[i].x/(double)n;return;
}
void mul(poly a,poly b){FFT(a.a,1,k);FFT(b.a,1,k);for(int i0;ik;i)a.a[i]a.a[i]*b.a[i];FFT(a.a,-1,k);return;
}
signed main()
{scanf(%d%d,m,n);scanf(%s,t);scanf(%s,s);for(int i0;in;i){char cs[i];int zs[i]-a1;if(c*)z0;F[0].a[i]complex(z*z*z,0);F[1].a[i]complex(z*z,0);F[2].a[i]complex(z,0);}for(int i0;im;i){char ct[m-i-1];int zc-a1;if(c*)z0;G[0].a[i]complex(z,0);G[1].a[i]complex(z*z,0);G[2].a[i]complex(z*z*z,0);}k1;for(k1;k2*n;)k1;for(int i0;ik;i)r[i](r[i1]1)|((i1)?(k1):0);mul(F[0],G[0]);mul(F[1],G[1]);mul(F[2],G[2]);for(int i0;ik;i)F[0].a[i].xF[0].a[i].x-2.0*F[1].a[i].xF[2].a[i].x;k0;for(int i0;in-m;i)if(fabs(F[0].a[im-1].x)0.5)k,q.push(i);printf(%d\n,k);while(!q.empty())printf(%d ,q.front()1),q.pop();return 0;
}
