quhengyi11 的博客

quhengyi11 的博客

题解 CF528D 【Fuzzy Search】

posted on 2019-02-27 21:57:08 | under 题解 |

是一道法法塔匹配字符串的经典套路题

我们首先知道我们可以把两个字符串先$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)$

#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);

}