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;
}