题解 CF528D 【Fuzzy Search】

是一道法法塔匹配字符串的经典套路题 我们首先知道我们可以把两个字符串先$01$化。将$b$串翻转然后跟$a$串做卷积就能弄出一个位置的匹配数 可是这题还有一个$k$，咋搞呢？ 我们可以知道，对于任意一个$a[i]=1$，我们可以令$a[i-k$到$i+k]=1$，显然这样与$b$卷积就解决了$k$的限定。 然后用一个$lf[i]$表示前面一个$1$的位置离当前位置$i$的距离，$rf[i]$表示后面一个$1$的位置离当前位置$i$的距离，然后$O(n)$预处理一下就行了。 总复杂度$O(4nlogn)$ ```cpp #include<bits/stdc++.h> #define N 600005 #define fo(i, a, b) for (R int i = (a); i <= (b); ++i) #define fd(i, a, b) for (R int i = (a); i >= (b); --i) #define in inline #define R register const double pi = acos(-1); int a[N], b[N], len, n, m; struct complex{ double real, imag; in void conj () { imag = -imag; } friend in complex operator * (const complex &x, const complex &y) { return (complex) {x.real * y.real - x.imag * y.imag, x.real * y.imag + x.imag * y.real}; } friend in complex operator + (const complex &x, const complex &y) { return (complex) {x.real + y.real, x.imag + y.imag}; } friend in complex operator - (const complex &x, const complex &y) { return (complex) {x.real - y.real, x.imag - y.imag}; } }c1[N], c2[N], omega[N], c3[N]; in void dft(complex *c, int len) { int k = 0; while ((1 << k) < len) ++k; --k; fo (i, 0, len) { int g = 0; fo (j, 0, k) if ((1 << j) & i) g |= (1 << k - j); if (i < g) std::swap(c[i], c[g]); } for (int l = 2; l <= len; l <<= 1) { int mid = l >> 1; for (complex *p = c; p != c + len; p += l) for (int i = 0; i < mid; ++i) { complex tmp = omega[len / l * i] * p[mid + i]; p[mid + i] = p[i] - tmp; p[i] = p[i] + tmp; } } } int mp[5], k, lf[N], rf[N]; char s1[N], s2[N]; int main() { scanf("%d %d %d", &n, &m, &k); mp[1] = 'A'; mp[2] = 'C'; mp[3] = 'G'; mp[4] = 'T'; scanf("%s", s1); scanf("%s", s2); int ans = 0; memset(c3, 0, sizeof c3); fo (l, 1, 4) { for (int i = 0; i < n; ++i) a[i] = (mp[l] == s1[i]); for (int i = 0; i < m; ++i) b[i] = (mp[l] == s2[i]); std::reverse(b, b + m); memset(lf, 0, sizeof lf); memset(rf, 0, sizeof rf); int sta = 0; while (sta < n && !a[sta]) lf[sta++] = 23333333; lf[sta] = 0; fo (i, sta + 1, n - 1) lf[i] = (a[i]) ? 0 : lf[i - 1] + 1; sta = n - 1; while (sta >= 0 && !a[sta]) rf[sta--] = 23333333; rf[sta] = 0; fd (i, sta - 1, 0) rf[i] = (a[i]) ? 0 : rf[i + 1] + 1; fo (i, 0, n - 1) if (std::min(lf[i], rf[i]) <= k) a[i] = 1; int len = 1; while (len <= n + m) len = len << 1; fo (i, 0, len) c1[i].real = c2[i].real = c1[i].imag = c2[i].imag = 0; for (int i = 0; i < n; ++i) c1[i].real = a[i]; for (int i = 0; i < m; ++i) c2[i].real = b[i]; fo (i, 0, len) omega[i] = (complex) {cos(2 * pi * i / len), sin(2 * pi * i / len)}; dft(c1, len); dft(c2, len); fo (i, 0, len) c1[i] = c1[i] * c2[i]; fo (i, 0, len) omega[i].conj(); dft(c1, len); fo (i, 0, len) c3[i].real += c1[i].real / len; } fo (i, 0, n + m) a[i] = (int) (c3[i].real + 0.5); fo (i, m - 1, n - 1) if (a[i] == m) ++ans; printf("%d\n", ans); } ```