c/c++语言开发共享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("%dn", 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 */