BZOJ4259: 残缺的字符串(FFT 字符串匹配)
程序员文章站
2023-02-21 12:51:49
题意 "题目链接" Sol 知道FFT能做字符串匹配的话这就是个裸题了吧。。 考虑把B翻转过来,如果$\sum_{k = 0}^M (B_{i k} A_k)^2 B_{i k} A_k = 0$ 那么说明能匹配。然后拆开三波FFT就行了 ......
题意
sol
知道fft能做字符串匹配的话这就是个裸题了吧。。
考虑把b翻转过来,如果\(\sum_{k = 0}^m (b_{i - k} - a_k)^2 * b_{i-k}*a_k = 0\)
那么说明能匹配。然后拆开三波fft就行了
/* */ #include<bits/stdc++.h> #define ll long long const int maxn = 1e6 + 10, inf = 1e9 + 7; using namespace std; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, m; ll g[maxn], f[maxn]; char sa[maxn], sb[maxn]; int ta[maxn], tb[maxn], a[maxn], b[maxn], rev[maxn], lim; ll sqr2(int x) {return 1ll * x * x;} ll sqr3(int x) {return 1ll * x * x * x;} const double pi = acos(-1); struct com { double x, y; com operator * (const com &rhs) const { return {x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x}; } com operator + (const com &rhs) const { return {x + rhs.x, y + rhs.y}; } com operator - (const com &rhs) const { return {x - rhs.x, y - rhs.y}; } }a[maxn], b[maxn]; void fft(com *a, int lim, int type) { for(int i = 0; i < lim; i++) if(i < rev[i]) swap(a[i], a[rev[i]]); for(int mid = 1; mid < lim; mid <<= 1) { com wn = {cos(pi / mid), type * sin(pi / mid)}; for(int i = 0; i < lim; i += (mid << 1)) { com w = {1, 0}; for(int j = 0; j < mid; j++, w = w * wn) { com x = a[i + j], y = w * a[i + j + mid]; a[i + j] = x + y; a[i + j + mid] = x - y; } } } if(type == -1) { for(int i = 0; i <= lim; i++) a[i].x /= lim; } } void mul(int *b, int *a) { memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); for(int i = 0; i < n; i++) b[i].x = b[i]; for(int i = 0; i < m; i++) a[i].x = a[i]; fft(b, lim, 1); fft(a, lim, 1); for(int i = 0; i < lim; i++) b[i] = b[i] * a[i]; fft(b, lim, -1); for(int i = m - 1; i <= n; i++) f[i] += round(b[i].x); } signed main() { //freopen("2.in", "r", stdin); freopen("b.out", "w", stdout); m = read(); n = read(); scanf("%s %s", sa, sb); for(int i = 0; i < m; i++) ta[i] = (sa[i] == '*' ? 0 : sa[i] - 'a' + 1); for(int i = 0; i < n; i++) tb[i] = (sb[i] == '*' ? 0 : sb[i] - 'a' + 1); reverse(tb, tb + n); int len = 0; lim = 1; while(lim <= n + m) len++, lim <<= 1; for(int i = 0; i < lim; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << len - 1); for(int i = 0; i < n; i++) b[i] = sqr3(tb[i]); for(int i = 0; i < m; i++) a[i] = ta[i]; mul(b, a); for(int i = 0; i < n; i++) b[i] = -2 * sqr2(tb[i]); for(int i = 0; i < m; i++) a[i] = sqr2(ta[i]); mul(b, a); for(int i = 0; i < n; i++) b[i] = tb[i]; for(int i = 0; i < m; i++) a[i] = sqr3(ta[i]); mul(b, a); int ans = 0; for(int i = m - 1; i < n; i++) if(!f[i]) ans++; printf("%d\n", ans); for(int i = n - 1; i >= m - 1; i--) if(!f[i]) printf("%d ", n - i); return 0; } /* 3 7 a*b aebr*ob */
上一篇: Node.js Mongodb 密码特殊字符 @的解决方法
下一篇: 榨汁机怎么用,你平日里会使用