Codeforces #296 Div1 D. Fuzzy Search
問題:
http://codeforces.com/contest/528/problem/D
問題概要は省略します.
典型なのかもしれないけど, あんまりこういうの解いたことなかったので面白かった
解法:
流石にまとめてマッチ箇所を求めるのは大変そうなので, 置く場所は全部試すことにする.
そこで判定を速く出来ればそれでOK
文字が4種類しかないので, 各場所で各文字について判定出来ればOK
まず, Sのi番目に文字Pをあわせるとき, [i-k,i+k]番目にPがあれば良い.
Sの各場所にPを合わせてよいかどうかの配列はimos法などで線形で計算出来る.
そしてTについても各文字がPか否かのbit列にする.
左端をi (0 <= i < |S|-|T|)番目に置いた時, bit演算風に書くとS[i,i+|T|-1] & T[0,|T|-1]がT[0,|T|-1]に等しければその文字Pについてマッチ可能.
よく考えるとこの処理は内積みたいな感じで,
sum S[i+j]*T[j] (0<=j<|T|)がT中の1の個数に等しければOKです.
ここでTをひっくり返したものをT'とすると, T'[|T|-1-j] = T[j]より
sum S[i+j]*T[j]=S[i+j]*T'[|T|-1-j] (0<=j<|T|)となり, これは添字の和が一定なので畳込みになっている
これはFFTで高速に計算出来る(非再帰FFTの中身は相変わらず知りません...)
計算量は結局0(NlogN) (Nは文字列長さ)
コード:
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; typedef long long ll; typedef vector<int> vi; #define pb push_back #define eb emplace_back #define mp make_pair #define fi first #define se second #define rep(i,n) rep2(i,0,n) #define rep2(i,m,n) for(int i=m;i<(n);i++) #define ALL(c) (c).begin(),(c).end() typedef double Num; const Num PI = acos(-1.0); typedef complex<Num> Complex; void fft_main(int n, Num theta, Complex a[]) { for (int m = n; m >= 2; m >>= 1) { int mh = m >> 1; Complex thetaI = Complex(0, theta); rep(i, mh) { Complex w = exp((Num)i * thetaI); for (int j = i; j < n; j += m) { int k = j + mh; Complex x = a[j] - a[k]; a[j] += a[k]; a[k] = w * x; } } theta *= 2; } int i = 0; for (int j = 1; j < n - 1; ++j) { for (int k = n >> 1; k > (i ^= k); k >>= 1) ; if (j < i) swap(a[i], a[j]); } } void fft(int n, Complex a[]) { fft_main(n, 2 * PI / n, a); } void inverse_fft(int n, Complex a[]) { fft_main(n, -2 * PI / n, a); } void convolution(vector<Complex> &v, vector<Complex> &w) { int n = 1, vwn = v.size() + w.size() - 1; while (n < vwn) n <<= 1; v.resize(n), w.resize(n); fft(n, &v[0]); fft(n, &w[0]); rep(i, n) v[i] *= w[i]; inverse_fft(n, &v[0]); rep(i, n) v[i] /= n; } string S, T; int w; int l1, l2; int imos[200010]; int ok[200010]; const string gen = "AGCT"; int main() { cin >> l1 >> l2 >> w; cin >> S >> T; reverse(ALL(T)); for (char c : gen) { memset(imos, 0, sizeof(imos)); rep(i, l1) { if (S[i] == c) { int l = max(i - w, 0); int r = min(i + w + 1, l1); ++imos[l]; --imos[r]; } } vector<Complex> v1, v2; rep(i, l1) { imos[i + 1] += imos[i]; int f = !!imos[i]; v1.pb(f); } int num = 0; rep(i, l2) { int f = T[i] == c; v2.pb(f); num += f; } convolution(v1, v2); for (int i = 0; i <= l1 - l2; ++i) { ok[i] += (int)(v1[i + l2 - 1].real() + 0.5) == num; } } int ret = 0; for (int i = 0; i <= l1 - l2; ++i) { ret += (ok[i] == 4); } cout << ret << endl; return 0; }