省队集训 Day1 残缺的字符串

时间：2021-12-24 10:10:48

【题目大意】

双串带通配符匹配。

$|S|, |T| \leq 5 * 10^5$

TL: 2s

【题解】

参考bzoj 4503

可以设计如下函数 A[i] * B[i] * (A[i] - B[i])^2

如果有通配符，A[i] = 0，否则，A[i] = s[i] - 'a' + 1；B同理。

可以自行验证，这是一种很妙的设计。

然后就是卷积的事情了。大概做9次DFT。

可以用类似于MTT的技巧搞到4次，不会写。

# include <math.h>

# include <stdio.h>

# include <string.h>

# include <iostream>

# include <algorithm>

// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

const int M = 5e5 + , N = 2e6 + ;

const int mod = 1e9+;

const ld pi = acos(-1.0);

char s[M], t[M];

int A[M], B[M], ns, nt;

struct cp {

    ld x, y;

    cp() {}

    cp(ld x, ld y) : x(x), y(y) {}

    friend cp operator + (cp a, cp b) {

        return cp(a.x + b.x, a.y + b.y);

    }

    friend cp operator - (cp a, cp b) {

        return cp(a.x - b.x, a.y - b.y);

    }

    friend cp operator * (cp a, cp b) {

        return cp(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);

    }

}a[N], b[N], ans[N];

namespace FFT {

    int n, lst[N]; cp w[][N];

    inline void set(int _n) {

        n = ;

        while(n < _n) n <<= ;

        for (int i=; i<n; ++i) w[][i] = cp(cos(pi *  / n * i), sin(pi *  / n * i)), w[][i] = cp(w[][i].x, -w[][i].y);

        int len = ;

        while((<<len) < n) ++len;

        for (int i=; i<n; ++i) {

            int t = ;

            for (int j=; j<len; ++j) if(i & (<<j)) t |= (<<(len-j-));

            lst[i] = t;

        }

    }

    inline void DFT(cp *a, int op) {

        cp *o = w[op];

        for (int i=; i<n; ++i) if(i < lst[i]) swap(a[i], a[lst[i]]);

        for (int len=; len<=n; len<<=) {

            int m = len>>;

            for (cp *p=a; p!=a+n; p+=len) {

                for (int k=; k<m; ++k) {

                    cp t = o[n/len*k] * p[k+m];

                    p[k+m] = p[k] - t;

                    p[k] = p[k] + t;

                }

            }

        }

        if(op) {

            for (int i=; i<n; ++i) a[i].x /= (ld)n, a[i].y /= (ld)n;

        }

    }

}

# define L FFT::n

int main() {

    scanf("%s%s", t, s); ns = strlen(s), nt = strlen(t);

    for (int i=; i<ns; ++i) A[i] = (s[i] == '*' ?  : s[i] - 'a' + );

    for (int i=; i<nt; ++i) B[i] = (t[i] == '*' ?  : t[i] - 'a' + );

    reverse(B, B+nt);

    // (A[i] - B[i])^2 * A[i] * B[i]  =  A[i]^3 * B[i] + A[i] * B[i]^3 - A[i]^2 * B[i]^2

    FFT :: set(max(ns, nt));

    for (int i=; i<ns; ++i) a[i] = cp(A[i] * A[i] * A[i], );

    for (int i=ns; i<L; ++i) a[i] = cp(, );

    for (int i=; i<nt; ++i) b[i] = cp(B[i], );

    for (int i=nt; i<L; ++i) b[i] = cp(, );

    FFT :: DFT(a, ); FFT :: DFT(b, );

    for (int i=; i<L; ++i) ans[i] = ans[i] + a[i] * b[i];

    for (int i=; i<ns; ++i) a[i] = cp(A[i], );

    for (int i=ns; i<L; ++i) a[i] = cp(, );

    for (int i=; i<nt; ++i) b[i] = cp(B[i] * B[i] * B[i], );

    for (int i=nt; i<L; ++i) b[i] = cp(, );

    FFT :: DFT(a, ); FFT :: DFT(b, );

    for (int i=; i<L; ++i) ans[i] = ans[i] + a[i] * b[i];

    for (int i=; i<ns; ++i) a[i] = cp(A[i] * A[i] * , );

    for (int i=ns; i<L; ++i) a[i] = cp(, );

    for (int i=; i<nt; ++i) b[i] = cp(B[i] * B[i], );

    for (int i=nt; i<L; ++i) b[i] = cp(, );

    FFT :: DFT(a, ); FFT :: DFT(b, );

    for (int i=; i<L; ++i) ans[i] = ans[i] - a[i] * b[i];

    FFT :: DFT(ans, );

    for (int i=nt-; i<ns; ++i) {

        if((int)(ans[i].x-0.5) == ) printf("%d ", i-nt+);

    }

    puts("");

    return ;

}

可能是noi前最后一次复习FFT了。

相关文章