题解 P4173 【残缺的字符串】

Ameyax

2018-03-09 10:07:12

Solution

没人发标算,%楼下大佬 把$*$都改成$0$ 设$dis(A,B)=\sum\limits_{i=0}^{n-1}(A[i]-B[i])^2A[i]B[i]$ $B$以$i$结尾的串与$A$完全匹配的条件是$f[i]=dis(A,B[i-m+1,i])==0$ 翻转$A$串,并在末尾补$0$。 $$f[i]=\sum\limits_{j=0}^i(A[j]-B[i-j])^2A[j]B[i-j]$$ $$=\sum\limits_{j=0}^iA[j]^3B[i-j]-2\sum\limits_{j=0}^iA[j]^2B[i-j]^2+\sum\limits_{j=0}^iA[j]B[i-j]^3$$ 分三次$fft$出所有的$f[i]$,时间复杂度也是$O(nlogn)$但是比楼下大佬多了个$3$ 代码常数巨大 ```cpp #include <bits/stdc++.h> using namespace std; #define pi acos(-1) const int MAX = 1100000; char sa[MAX], sb[MAX]; int m, n, N, top, a[MAX], b[MAX]; int rev[MAX], sta[MAX]; struct cpx { double x, y; cpx() {} cpx(double xx, double yy) { x = xx, y = yy; } friend cpx operator * (cpx a, cpx b) { return cpx(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x); } friend cpx operator / (cpx a, double b) { return cpx(a.x / b, a.y / b); } friend cpx operator + (cpx a, cpx b) { return cpx(a.x + b.x, a.y + b.y); } friend cpx operator - (cpx a, cpx b) { return cpx(a.x - b.x, a.y - b.y); } friend cpx operator * (cpx a, double b) { return cpx(a.x * b, a.y * b); } }; cpx A[MAX], B[MAX], C[MAX]; void fft(cpx *a, int f) { for (int i = 0; i < N; i++) if (i < rev[i]) swap(a[i], a[rev[i]]); for (int i = 1; i < N; i <<= 1) { cpx wn(cos(pi / i), f * sin(pi / i)); for (int j = 0; j < N; j += (i << 1)) { cpx w(1, 0); for (int k = 0; k < i; k++) { cpx x = a[j + k], y = w * a[j + k + i]; a[j + k] = x + y; a[j + k + i] = x - y; w = w * wn; } } } if (f == -1) for (int i = 0; i < N; i++) a[i] = a[i] / N; } int main() { scanf("%d%d%s%s", &m, &n, sa, sb); int l = 0; for (N = 1; N < 2 * n; N <<= 1) l++; for (int i = 0; i < N; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1)); for (int i = 0; i < m; i++) if (sa[i] != '*') a[i] = sa[i] - 'a' + 1; for (int i = 0; i < n; i++) if (sb[i] != '*') b[i] = sb[i] - 'a' + 1; reverse(a, a + m); for (int i = 0; i < m; i++) A[i] = cpx(a[i] * a[i] * a[i], 0); for (int i = 0; i < n; i++) B[i] = cpx(b[i], 0); fft(A, 1); fft(B, 1); for (int i = 0; i < N; i++) C[i] = C[i] + A[i] * B[i]; for (int i = 0; i < N; i++) A[i] = B[i] = cpx(0, 0); for (int i = 0; i < m; i++) A[i] = cpx(a[i] * a[i], 0); for (int i = 0; i < n; i++) B[i] = cpx(b[i] * b[i], 0); fft(A, 1); fft(B, 1); for (int i = 0; i < N; i++) C[i] = C[i] - A[i] * B[i] * 2.0; for (int i = 0; i < N; i++) A[i] = B[i] = cpx(0, 0); for (int i = 0; i < m; i++) A[i] = cpx(a[i], 0); for (int i = 0; i < n; i++) B[i] = cpx(b[i] * b[i] * b[i], 0); fft(A, 1); fft(B, 1); for (int i = 0; i < N; i++) C[i] = C[i] + A[i] * B[i]; fft(C, -1); for (int i = m - 1; i < n; i++) if (fabs(C[i].x) < 0.5) sta[++top] = i - m + 2; printf("%d\n", top); for (int i = 1; i <= top; i++) printf("%d ", sta[i]); return 0; } 这题开6秒是闹哪样,bzoj上我用std::complex<double>都T掉了 上面的代码在bzoj跑了9s卡过 ```