CF528D Fuzzy Search

题意：给定k，只含有ACGT的字符串S和T，求T在S中出现了多少次。

字符匹配：如果S的[i - k, i + k]中有字符x，那么第i位可以匹配x。

解：

首先预处理：f[i][j]表示S的第i位能否匹配j。差分一下即可。

然后按照FFT的套路，枚举每种字符，算一遍有多少个匹配。四种字符加起来，如果匹配数等于T的长度，就匹配成功。

  1 #include <cstring>
  2 #include <cmath>
  3 #include <algorithm>
  4 #include <cstdio>
  5 const int N = 200010;
  6 const double pi = 3.1415926535897932384626;
  7 const char ch[] = {'A', 'C', 'G', 'T'};
  8 struct cp
  9 {
 10     double x, y;
 11     cp(double X = 0, double Y = 0)
 12     {
 13         x = X;
 14         y = Y;
 15     } inline cp operator +(const cp &w) const
 16     {
 17         return cp(x + w.x, y + w.y);
 18     } inline cp operator -(const cp &w) const
 19     {
 20         return cp(x - w.x, y - w.y);
 21     } inline cp operator *(const cp &w) const
 22     {
 23         return cp(x * w.x - y * w.y, x * w.y + y * w.x);
 24     }
 25 } a[N << 2], b[N << 2];
 26 int r[N << 2], ans[N << 2], f[N][4], d[N];
 27 char s[N], str[N];
 28 inline void FFT(int n, cp *a, int f)
 29 {
 30     for(int i = 0; i < n; i++)
 31     {
 32         if(i < r[i])
 33         {
 34             std::swap(a[i], a[r[i]]);
 35         }
 36     }
 37     for(int len = 1; len < n; len <<= 1)
 38     {
 39         cp Wn(cos(pi / len), f * sin(pi / len));
 40         for(int i = 0; i < n; i += (len << 1))
 41         {
 42             cp w(1, 0);
 43             for(int j = 0; j < len; j++)
 44             {
 45                 cp t = a[i + len + j] * w;
 46                 a[i + len + j] = a[i + j] - t;
 47                 a[i + j] = a[i + j] + t;
 48                 w = w * Wn;
 49             }
 50         }
 51     }
 52     if(f == -1)
 53     {
 54         for(int i = 0; i <= n; i++)
 55         {
 56             a[i].x /= n;
 57         }
 58     }
 59     return;
 60 }
 61 int main()
 62 {
 63     int n, m, k;
 64     scanf("%d%d%d", &n, &m, &k);
 65     n--;
 66     m--;
 67     scanf("%s%s", s, str);
 68     for(int i = 0; i < 4; i++)
 69     {
 70         for(int j = 0; j <= n; j++)
 71         {
 72             if(s[j] == ch[i])
 73             {
 74                 d[std::max(0, j - k)]++;
 75                 d[std::min(n + 1, j + k + 1)]--;
 76             }
 77         }
 78         int now = 0;
 79         for(int j = 0; j <= n; j++)
 80         {
 81             now += d[j];
 82             if(now)
 83             {
 84                 f[j][i] = 1;
 85             }
 86         }
 87         memset(d, 0, sizeof(d));
 88     }
 89     int len = 2, lm = 1;
 90     while(len <= n + m)
 91     {
 92         len <<= 1;
 93         lm++;
 94     }
 95     for(int i = 1; i <= len; i++)
 96     {
 97         r[i] = (r[i >> 1] >> 1) | ((i & 1) << (lm - 1));
 98     }
 99     for(int i = 0; i < 4; i++)
100     {
101         for(int j = 0; j <= len; j++)
102         {
103             a[j] = b[j] = cp(0, 0);
104         }
105         for(int j = 0; j <= n; j++)
106         {
107             a[j].x = f[j][i];
108         }
109         for(int j = 0; j <= m; j++)
110         {
111             b[m - j].x = (int)(str[j] == ch[i]);
112         }
113         FFT(len, a, 1);
114         FFT(len, b, 1);
115         for(int j = 0; j <= len; j++)
116         {
117             a[j] = a[j] * b[j];
118         }
119         FFT(len, a, -1);
120         for(int j = 0; j <= len; j++)
121         {
122             ans[j] += (int)(a[j].x + 0.5);
123         }
124     }
125     int temp = 0;
126     for(int i = m; i <= n; i++)
127     {
128         if(ans[i] == m + 1)
129         {
130             temp++;
131         }
132     }
133     printf("%d
", temp);
134     return 0;
135 }

AC代码

代码乱了，用了CB的格式化，码风可能有点奇怪...