BZOJ4259: 残缺的字符串(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
*/