做求职网站,服装网站网络建设和硬件资源,今天的新闻是什么,外贸怎样做网站解析
通配符匹配的经典题。 设单词串为 AAA,文章串为 BBB。 把 AAA 翻转一下#xff0c;判断问题就能转化为一个卷积的形式#xff1a; F(p)i0m−1match(Ai1,Bp−i)F(p)\_{i0}^{m-1}match(A_{i1},B_{p-i})F(p)i0m−1match(Ai1,Bp−i) match(a,b)match(…解析
通配符匹配的经典题。 设单词串为 AAA,文章串为 BBB。 把 AAA 翻转一下判断问题就能转化为一个卷积的形式 F(p)i0m−1match(Ai1,Bp−i)F(p)\_{i0}^{m-1}match(A_{i1},B_{p-i})F(p)i0m−1match(Ai1,Bp−i) match(a,b)match(a,b)match(a,b) 表示 a,ba,ba,b 两个字符是否互相匹配。 但是这么丑的东西显然难以优化我们需要更优美的表达形式。 考虑且运算的性质我们需要一个非法就能检测出非法那么我们考虑利用平方的非负性设计一个函数 C(a,b)(a−b)2C(a,b)(a-b)^2C(a,b)(a−b)2把函数改写成 F(p)∑i0m−1C(Ai1,Bp−i)F(p)\sum_{i0}^{m-1}C(A_{i1},B_{p-i})F(p)i0∑m−1C(Ai1,Bp−i) 位置合法当且仅当对应函数值为0把平方拆开分别算再加起来即可。
现在考虑如何加入通配符。 只要 a,ba,ba,b 中有任意一个是通配符就应该是合法的。 利用 000 乘任何数都是 000 的性质对于 CCC 函数进行微调 C(a,b)(a−b)2jd(a)jd(b)C(a,b)(a-b)^2jd(a)jd(b)C(a,b)(a−b)2jd(a)jd(b) 其中 jd(a)jd(a)jd(a) 表示字符 aaa 是否不是 *。 这样就可以卷起来算了。
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
inline ll read() {ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}
const int N2e6100;
const int mod998244353;
int n,m,k;
inline ll ksm(ll x,ll k){ll res1;while(k){if(k1) resres*x%mod;xx*x%mod;k1;}return res;
}
int r[N];
void init(int n,int lim){lim1;int L0;while(limn) lim1,L;for(int i1;ilim;i) r[i](r[i1]1)|((i1)(L-1));
}
void NTT(ll *x,int lim,int op){for(int i0;ilim;i) if(ir[i]) swap(x[i],x[r[i]]);for(int l1;llim;l1){ll wksm(3,(mod-1)/(l1));if(op-1) wksm(w,mod-2);for(int st0;stlim;st(l1)){for(ll i0,now1;il;i,nownow*w%mod){ll ux[sti],vnow*x[stil]%mod;x[sti]uvmod?uv-mod:uv;x[stil]u-v0?u-vmod:u-v;}}}if(op-1){ll niksm(lim,mod-2);for(int i0;ilim;i) x[i]x[i]*ni%mod;}return;
}
void copy(ll *a,ll *b,int n,int lim){assert(nlim);memcpy(a,b,sizeof(ll)*n);fill(an,alim,0);return;
}
void mul(ll *a,ll *b,ll *c,int n,int m){static ll u[N],v[N];static int lim;//for(int i0;in;i) printf(%lld ,a[i]);putchar(\n);//for(int i0;im;i) printf(%lld ,b[i]);putchar(\n);init(nm-1,lim);copy(u,a,n,lim);copy(v,b,m,lim);NTT(u,lim,1);NTT(v,lim,1);for(int i0;ilim;i) c[i]u[i]*v[i]%mod;NTT(c,lim,-1);//for(int i0;inm-1;i) printf(%lld ,c[i]);putchar(\n);//putchar(\n);return;
}
void inv(ll *h,ll *f,int n){static ll t1[N],t2[N];static int lim;if(n1){f[0]ksm(h[0],mod-2);return;}inv(h,f,(n1)1);init(n1,lim);fill(f((n1)1),flim,0);copy(t1,f,n,lim);copy(t2,h,n,lim);NTT(t1,lim,1);NTT(t2,lim,1);for(int i0;ilim;i) t1[i](2*t1[i]-t1[i]*t1[i]%mod*t2[i]%modmod)%mod;NTT(t1,lim,-1);memcpy(f,t1,sizeof(ll)*n);return;
}
//499122177
void Sqrt(ll *h,ll *f,int n){static ll t1[N],t2[N];static int lim;if(n1){f[0]1;return;}Sqrt(h,f,(n1)1);init(n1,lim);fill(f((n1)1),flim,0);inv(f,t1,n);fill(t1n,t1lim,0);mul(h,t1,t1,n,n);copy(t2,f,n,lim);NTT(t1,lim,1);NTT(t2,lim,1);for(int i0;ilim;i) t1[i](t1[i]t2[i]%mod)*499122177%mod;NTT(t1,lim,-1);memcpy(f,t1,sizeof(ll)*n);return;
}
void dao(ll *h,ll *f,int n){static ll t[N];static int lim;init(n1,lim);copy(t,h,n,lim);f[n-1]0;for(int i0;in-1;i) f[i]t[i1]*(i1)%mod;fill(fn,flim,0);return;
}
void jifen(ll *h,ll *f,int n){static ll t[N];static int lim;init(n1,lim);copy(t,h,n,lim);f[0]0;for(int i1;in;i) f[i]h[i-1]*ksm(i,mod-2)%mod;fill(fn,flim,0);
}
void Ln(ll *h,ll *f,int n){static ll t1[N],t2[N];static int lim;init(n1,lim);inv(h,t1,n);fill(t1n,t1lim,0);dao(h,t2,n);mul(t1,t2,t1,n,n);jifen(t1,f,n);return;
}
void Exp(ll *h,ll *f,int n){static ll t1[N],t2[N],t3[N];static int lim;if(n1){f[0]1;return;}Exp(h,f,(n1)1);init(n1,lim);fill(f((n1)1),flim,0);copy(t1,f,n,lim);copy(t2,h,n,lim);Ln(f,t3,n);fill(t3n,t3lim,0);NTT(t1,lim,1);NTT(t2,lim,1);NTT(t3,lim,1);for(int i0;ilim;i) t1[i]t1[i]*(1t2[i]-t3[i]mod)%mod;NTT(t1,lim,-1);memcpy(f,t1,sizeof(ll)*n);return;
}
ll a[N],b[N],c[N],res[N];
bool x[N],y[N];
char s1[N],s2[N];
int ans[N],tot;
signed main() {
#ifndef ONLINE_JUDGE//freopen(a.in,r,stdin);//freopen(a.out,w,stdout);
#endif
//printf(%d\n,sizeof(a1)/1024/1024);mread();nread();scanf( %s %s,s11,s21);for(int l1,rm;lr;l,r--) swap(s1[l],s1[r]);for(int i1;im;i) x[i](s1[i]!*),s1[i]-a-1;for(int i1;in;i) y[i](s2[i]!*),s2[i]-a-1;for(int i1;im;i) a[i]s1[i]*s1[i]*x[i];for(int i1;in;i) b[i]y[i];mul(a,b,c,m1,n1);for(int i1;in1;i) res[i]c[i];for(int i1;im;i) a[i]x[i];for(int i1;in;i) b[i]s2[i]*s2[i]*y[i];mul(a,b,c,m1,n1);for(int i1;in1;i) res[i]c[i];for(int i1;im;i) a[i]s1[i]*x[i];for(int i1;in;i) b[i]s2[i]*y[i];mul(a,b,c,m1,n1);for(int i1;in1;i) res[i]-2*c[i];for(int pm;pn;p) if(res[p1]0) ans[tot]p-m1;printf(%d\n,tot);for(int i1;itot;i) printf(%d ,ans[i]);return 0;
}
/*
4
0 1 1
*/
