汽车专业网站,手机网站底部广告代码,百度网址ip地址,扬州百度seo传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你两个长度为m,nm,nm,n的串a,ba,ba,b#xff0c;问你bbb串中每个长度为mmm的连续字串能否与aaa完全匹配#xff0c;其中含有通配符∗*∗#xff0c;输出每个位置的开头。 n,m≤3e5n,m\le3e5n,m≤3e5
思…传送门
文章目录题意思路题意
给你两个长度为m,nm,nm,n的串a,ba,ba,b问你bbb串中每个长度为mmm的连续字串能否与aaa完全匹配其中含有通配符∗*∗输出每个位置的开头。 n,m≤3e5n,m\le3e5n,m≤3e5
思路
比较容易想到魔改kmpkmpkmp但是你会发现怎么改都aaa不掉这个题。 先不考虑通配符定义c(x,y)c(x,y)c(x,y)表示ax−bya_x-b_yax−by显然c(x,y)0c(x,y)0c(x,y)0时代表axa_xax与byb_yby这个位置匹配。 定义函数f(x)∑i0m−1C(i,x−mi1)f(x)\sum_{i0}^{m-1}C(i,x-mi1)f(x)∑i0m−1C(i,x−mi1)我们发现不能根据f(x)f(x)f(x)是否为000来判断是否匹配因为有ab,baab,baab,ba这种串。不难发现问题就是出现了负数我们考虑将其加个绝对值绝对值不是很好处理所以考虑给他加一个平方即f(x)∑i0m−1(A(i)−B(x−mi1))2f(x)\sum_{i0}^{m-1}(A(i)-B(x-mi1))^2f(x)∑i0m−1(A(i)−B(x−mi1))2这个狮子已经很像FFTFFTFFT了考虑将其展开f(x)∑i0m−1A(i)2∑i0m−1B(x−mi1)2−2∗∑i0m−1A(i)∗B(x−mi1)f(x)\sum_{i0}^{m-1}A(i)^2\sum_{i0}^{m-1}B(x-mi1)^2-2*\sum_{i0}^{m-1}A(i)*B(x-mi1)f(x)∑i0m−1A(i)2∑i0m−1B(x−mi1)2−2∗∑i0m−1A(i)∗B(x−mi1)前面两项很好处理只有最后这一项不是很好看考虑将AAA串翻转一下即∑i0m−1A(m−i−1)∗B(x−mi1)\sum_{i0}^{m-1}A(m-i-1)*B(x-mi1)∑i0m−1A(m−i−1)∗B(x−mi1)观察一下这不就是个卷积即g(x)∑ijxA(i)∗B(j)g(x)\sum_{ijx}A(i)*B(j)g(x)∑ijxA(i)∗B(j)所以卷一下就好啦。 有通配符怎么办呢 按照上面的思路我们是将相等的数变成了000所以我们只需要改一下C(x,y)C(x,y)C(x,y)的定义改为C(x,y)(Ax−By)2AxByC(x,y)(A_x-B_y)^2A_xB_yC(x,y)(Ax−By)2AxBy即当某个位置是通配符的时候将这个位置的A,BA,BA,B都赋值为000即可。 推导方法与上面相同这里直接给出答案f(x)∑ijxA(x)3B(x)∑ijxA(x)B(x)3−2∗∑ijxA(x)2B(x)2f(x)\sum_{ijx}A(x)^3B(x)\sum_{ijx}A(x)B(x)^3-2*\sum_{ijx}A(x)^2B(x)^2f(x)ijx∑A(x)3B(x)ijx∑A(x)B(x)3−2∗ijx∑A(x)2B(x)2 做666次即可。 小优化由于最终只用到了前nnn项所以卷的长度定义为nnn的最小222的幂次即可。 不加这个优化很可能过不了需要换NTTNTTNTT。
// Problem: P4173 残缺的字符串
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4173
// Memory Limit: 128 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N6000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6,PIacos(-1);int n,m;
int rev[N];
int bit,limit;
int A[N],B[N];
char s1[N],s2[N];
double p1[N],p2[N];struct Complex {double x,y;Complex operator (const Complex t) const { return {xt.x,yt.y}; }Complex operator - (const Complex t) const { return {x-t.x,y-t.y}; }Complex operator * (const Complex t) const { return {x*t.x-y*t.y,x*t.yy*t.x}; }
}a[N],b[N],c[N],d[N],ans[N];void fft(Complex a[],int inv) {for(int i0;ilimit;i) if(irev[i]) swap(a[i],a[rev[i]]);for(int mid1;midlimit;mid1) {Complex w1Complex({p1[mid],inv*p2[mid]});for(int i0;ilimit;imid*2) {Complex wkComplex({1,0});for(int j0;jmid;j,wkwk*w1) {Complex xa[ij],ywk*a[ijmid];a[ij]xy; a[ijmid]x-y;}}}
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);cinmns1s2;for(int i0;im;i) A[i]s1[i]*? 0:s1[i]-a1;for(int i0;in;i) B[i]s2[i]*? 0:s2[i]-a1;reverse(A,Am);while((1bit)n) bit;limit1bit;for(int i0;ilimit;i) rev[i](rev[i1]1)|((i1)(bit-1));for(int mid1;midlimit;mid1) p1[mid]cos(PI/mid),p2[mid]sin(PI/mid);for(int i0;im;i) a[i]{1.0*A[i]*A[i]*A[i],0},c[i]{1.0*A[i]*A[i],0};for(int i0;in;i) b[i]{1.0*B[i],0},d[i]{1.0*B[i]*B[i],0};fft(a,1); fft(b,1); fft(c,1); fft(d,1);Complex now{2,0};for(int i0;ilimit;i) ans[i]ans[i]a[i]*b[i]-c[i]*d[i]*now;for(int i0;ilimit;i) a[i]b[i]{0,0};for(int i0;im;i) a[i]{1.0*A[i],0};for(int i0;in;i) b[i]{1.0*B[i]*B[i]*B[i],0};fft(a,1); fft(b,1); for(int i0;ilimit;i) ans[i]ans[i]a[i]*b[i];fft(ans,-1);vectorintv;for(int im-1;in;i) if((fabs(ans[i].x/limit))0.5) v.pb(i-m2);printf(%d\n,v.size());for(auto x:v) printf(%d ,x);return 0;
}
/**/
