【CF528D】Fuzzy Search

第一次做这种多项式搞字符串的题目,写一下吧

a_i = [s_i 能与 c 匹配],b_i = [t_i = c]
然后对于s串从第i位开始和t串匹配来说

f_i = \sum_{j=0}^{m-1}a_{i+j}b_{j}

这样没法卷积了,因此我们将字符串翻转成m-j-1,然后就变成了可以卷记的形式。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;  
}

typedef long long lo;

template <typename int_qwq>

inline void re(int_qwq &x)
{
    x = 0;
    char a;
    bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b)
        x = - x;
}

const int mo = 998244353;

const int ms = 5e5 + 10;

int n, m, K, len, a[ms << 2], b[ms << 2], pos[ms << 2], po[ms << 2], inv[ms << 2], cnt[ms << 2];

char s1[ms], s2[ms];

inline int ksm(int x, int k)
{
    int rt = 1, a = x;
    for(; k; a = 1ll * a * a % mo, k >>= 1)
        if(k & 1)
            rt = 1ll * rt * a % mo;
    return rt;
}

inline void ntt(int *a, int len, int tp)
{
    for(ri i = 1; i < len; i ++)
        if(i < pos[i])
            swap(a[i], a[pos[i]]);
    int la, lb, w, wn;
    for(ri i = 1; i < len; i <<= 1)
    {
        wn = (tp == 1) ? po[i] : inv[i];
        for(ri j = 0; j < len; j += (i << 1))
        {
            w = 1;
            for(ri k = j; k < j + i; k ++)
            {
                la = a[k], lb = 1ll * w * a[k + i] % mo, w = 1ll * w * wn % mo;
                a[k] = la + lb, a[k + i] = la - lb, a[k] -= (a[k] >= mo) ? mo : 0, a[k + i] += (a[k + i] < 0) ? mo : 0;
            }
        }
    }
    if(tp == -1)
    {
        int invlen = ksm(len, mo - 2);
        for(ri i = 0; i < len; i ++)
            a[i] = 1ll * a[i] * invlen % mo;
    }
}

inline void solve(char c)
{
    int las = -1e9 + 7;
    memset(a, 0, sizeof(a)), memset(b, 0, sizeof(b));
    for(ri i = 0; i < n; i ++)
    {
        if(s1[i] == c)
            las = i;
        if(i - las <= K)
            a[i] = 1;
    }
    las = 1e9 + 7;
    for(ri i = n - 1; i >= 0; i --)
    {
        if(s1[i] == c)
            las = i;
        if(las - i <= K)
            a[i] = 1;
    }
    for(ri i = 0; i < m; i ++)
        if(s2[i] == c)
            b[i] = 1;
    reverse(b, b + m);
    ntt(a, len, 1), ntt(b, len, 1);
    for(ri i = 0; i < len; i ++)
        a[i] = 1ll * a[i] * b[i] % mo;
    ntt(a, len, -1);
    for(ri i = 0; i < len; i ++)
        cnt[i] += a[i];
}

int main()
{
    re(n), re(m), re(K);
    len = 1; int num = 0;
    while(len < ((n + m) << 1))
        len <<= 1, num ++;
    for(ri i = 1; i < len; i ++)
        pos[i] = ((pos[i >> 1] >> 1) | ((i & 1) << (num - 1)));
    for(ri i = 1; i <= len; i <<= 1)
        po[i] = ksm(3, ((mo - 1) / (i << 1)));
    int inv3 = ksm(3, mo - 2);
    for(ri i = 1; i <= len; i <<= 1)
        inv[i] = ksm(inv3, ((mo - 1) / (i << 1)));
    scanf("%s%s", s1, s2);
    for(ri i = 0; i < 4; i ++)
        solve("ACGT"[i]);
    int pri = 0;
    for(ri i = 0; i < n + m - 1; i ++)
        pri += cnt[i] == m;
    printf("%d", pri);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注