网站配色 蓝色,网搜网,做外贸有哪些网站平台,有限公司简介4259: 残缺的字符串 题意#xff1a;s,t#xff0c;星号任意字符#xff0c;匹配方案数 和上题一样 多乘上一个\(a_{ji}\)就行了 #include iostream
#include cstdio
#include cstring
#include algorithm
#include cmath
using na…4259: 残缺的字符串 题意s,t星号任意字符匹配方案数 和上题一样 多乘上一个\(a_{ji}\)就行了 #include iostream
#include cstdio
#include cstring
#include algorithm
#include cmath
using namespace std;
typedef long long ll;
const int N(120)5;
const double PIacos(-1);
inline int read(){char cgetchar();int x0,f1;while(c0||c9){if(c-)f-1;cgetchar();}while(c0c9){xx*10c-0;cgetchar();}return x*f;
}struct meow{double x, y;meow(double a0, double b0):x(a), y(b){}
};
meow operator (meow a, meow b) {return meow(a.xb.x, a.yb.y);}
meow operator -(meow a, meow b) {return meow(a.x-b.x, a.y-b.y);}
meow operator *(meow a, meow b) {return meow(a.x*b.x-a.y*b.y, a.x*b.ya.y*b.x);}
meow conj(meow a) {return meow(a.x, -a.y);}
typedef meow cd;namespace FFT{int n, rev[N];void ini(int lim) {n1; int k0;while(nlim) n1, k;for(int i0; in; i) rev[i] (rev[i1]1) | ((i1)(k-1));}void dft(cd *a, int flag) {for(int i0; in; i) if(irev[i]) swap(a[i], a[rev[i]]);for(int l2; ln; l1) {int ml1; cd wn meow(cos(2*PI/l), flag*sin(2*PI/l));for(cd *pa; p!an; pl) {cd w(1, 0);for(int k0; km; k) {cd t w*p[km];p[km] p[k] - t;p[k] p[k] t;ww*wn;}}}if(flag-1) for(int i0; in; i) a[i].x/n;}
}using FFT::dft; using FFT::ini;int n, m, lim;
cd a[N], b[N], a2[N], b2[N], a3[N], b3[N], c[N];
char s[N], t[N];
int ans, li[N];
int main() {freopen(in,r,stdin);mread(); nread(); limnm-1; ini(lim);scanf(%s%s,t,s);for(int i0; in; i) s[i] s[i]* ? 0 : s[i]-a1;for(int i0; im; i) t[i] t[i]* ? 0 : t[i]-a1;for(int i0; in; i) a[i].x s[i], a2[i].x 2*s[i]*s[i], a3[i].x s[i]*s[i]*s[i];for(int i0; im; i) b[m-1-i].x t[i], b2[m-1-i].x t[i]*t[i], b3[m-1-i].x t[i]*t[i]*t[i];dft(a, 1); dft(a2, 1); dft(a3, 1); dft(b, 1); dft(b2, 1); dft(b3, 1);for(int i0; iFFT::n; i) c[i] a3[i]*b[i] - a2[i]*b2[i] a[i]*b3[i];dft(c, -1);for(int i0; in-m; i) if(floor(c[m-1i].x0.5)0) li[ans]i;printf(%d\n,ans);for(int i1; ians; i) printf(%d ,li[i]1);
} 转载于:https://www.cnblogs.com/candy99/p/6648749.html
