欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

BZOJ4259: 残缺的字符串(FFT 字符串匹配)

程序员文章站 2023-02-21 12:51:49
题意 "题目链接" Sol 知道FFT能做字符串匹配的话这就是个裸题了吧。。 考虑把B翻转过来,如果$\sum_{k = 0}^M (B_{i k} A_k)^2 B_{i k} A_k = 0$ 那么说明能匹配。然后拆开三波FFT就行了 ......

题意

题目链接

sol

知道fft能做字符串匹配的话这就是个裸题了吧。。

考虑把b翻转过来,如果\(\sum_{k = 0}^m (b_{i - k} - a_k)^2 * b_{i-k}*a_k = 0\)

那么说明能匹配。然后拆开三波fft就行了

/*

*/
#include<bits/stdc++.h>
#define ll long long 
const int maxn = 1e6 + 10, inf = 1e9 + 7;
using namespace std;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, m;
ll g[maxn], f[maxn];
char sa[maxn], sb[maxn];
int ta[maxn], tb[maxn], a[maxn], b[maxn], rev[maxn], lim;
ll sqr2(int x) {return 1ll * x * x;}
ll sqr3(int x) {return 1ll * x * x * x;}
const double pi = acos(-1);
struct com {
    double x, y;
    com operator * (const com &rhs) const {
        return {x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x};
    }
    com operator + (const com &rhs) const {
        return {x + rhs.x, y + rhs.y};
    }
    com operator - (const com &rhs) const {
        return {x - rhs.x, y - rhs.y};
    }
}a[maxn], b[maxn];
void fft(com *a, int lim, int type) {
    for(int i = 0; i < lim; i++) if(i < rev[i]) swap(a[i], a[rev[i]]);
    for(int mid = 1; mid < lim; mid <<= 1) {
        com wn = {cos(pi / mid), type * sin(pi / mid)};
        for(int i = 0; i < lim; i += (mid << 1)) {
            com w = {1, 0}; 
            for(int j = 0; j < mid; j++, w = w * wn) {
                com x = a[i + j], y = w * a[i + j + mid];
                a[i + j] = x + y;
                a[i + j + mid] = x - y;
            }
        }
    }
    if(type == -1) {
        for(int i = 0; i <= lim; i++) a[i].x /= lim;
    }
}
void mul(int *b, int *a) {
    memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b));
    for(int i = 0; i < n; i++) b[i].x = b[i];
    for(int i = 0; i < m; i++) a[i].x = a[i];
    fft(b, lim, 1);
    fft(a, lim, 1);
    for(int i = 0; i < lim; i++) b[i] = b[i] * a[i];
    fft(b, lim, -1);
    for(int i = m - 1; i <= n; i++) 
        f[i] += round(b[i].x);
}
signed main() {
    //freopen("2.in", "r", stdin);  freopen("b.out", "w", stdout);
    m = read(); n = read();
    scanf("%s %s", sa, sb);
    for(int i = 0; i < m; i++) ta[i] = (sa[i] == '*' ? 0 : sa[i] - 'a' + 1);
    for(int i = 0; i < n; i++) tb[i] = (sb[i] == '*' ? 0 : sb[i] - 'a' + 1);
    reverse(tb, tb + n);

    int len = 0; lim = 1;
    while(lim <= n + m) len++, lim <<= 1;
    for(int i = 0; i < lim; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << len - 1);
    
    for(int i = 0; i < n; i++) b[i] = sqr3(tb[i]);
    for(int i = 0; i < m; i++) a[i] = ta[i]; 
    mul(b, a);
    
    for(int i = 0; i < n; i++) b[i] = -2 * sqr2(tb[i]);
    for(int i = 0; i < m; i++) a[i] = sqr2(ta[i]);
    mul(b, a);

    for(int i = 0; i < n; i++) b[i] = tb[i];
    for(int i = 0; i < m; i++) a[i] = sqr3(ta[i]);
    mul(b, a);  
    
    int ans = 0;
    for(int i = m - 1; i < n; i++) 
        if(!f[i]) ans++;

    printf("%d\n", ans);

    for(int i = n - 1; i >= m - 1; i--) 
        if(!f[i]) 
            printf("%d ", n - i);
    
    return 0;
}
/*
3 7
a*b
aebr*ob
*/