【TJOI2017】DNA

题面

题解

对字符串一脸懵的我肯定只能用$FFT$这种暴力方法水过啊。。。

将后面那个字符串翻转一下，对$\text{AGCT}$分别统计，用$FFT$就可以啦

代码

#include<cstdio>

#include<cstring>

#include<cctype>

#include<cmath>

#include<algorithm>

#define RG register

const int maxn(200010);

const double pi(acos(-1));

const char DNA[] = "AGCT";

struct complex { double x, y; } A[maxn], B[maxn];

inline complex operator + (const complex &lhs, const complex &rhs)

	{ return (complex) {lhs.x + rhs.x, lhs.y + rhs.y}; }

inline complex operator - (const complex &lhs, const complex &rhs)

	{ return (complex) {lhs.x - rhs.x, lhs.y - rhs.y}; }

inline complex operator * (const complex &lhs, const complex &rhs)

{

	return (complex) {lhs.x * rhs.x - lhs.y * rhs.y,

		lhs.y * rhs.x + lhs.x * rhs.y};

}

char C[maxn], S[maxn];

int n, m, ans[maxn], N, r[maxn], P, T;

template<int opt> void FFT(complex *p)

{

	for(RG int i = 1; i < N; i++) if(i < r[i]) std::swap(p[i], p[r[i]]);

	for(RG int i = 1; i < N; i <<= 1)

	{

		complex rot = (complex) {cos(pi / i), opt * sin(pi / i)};

		for(RG int j = 0; j < N; j += i << 1)

		{

			complex w = (complex) {1, 0};

			for(RG int k = 0; k < i; ++k, w = w * rot)

			{

				complex x = p[j + k], y = w * p[i + j + k];

				p[j + k] = x + y, p[i + j + k] = x - y;

			}

		}

	}

}

int main()

{

	scanf("%d", &T);

	while(T--)

	{

		scanf("%s%s", C, S);

		n = strlen(C), m = strlen(S); std::reverse(S, S + m);

		for(N = 1, P = 0; N < n + m; N <<= 1, ++P);

		std::fill(ans, ans + n, 0);

		for(RG int i = 1; i < N; i++)

			r[i] = (r[i >> 1] >> 1) | ((i & 1) << (P - 1));

		for(RG int p = 0; p < 4; ++p)

		{

			for(RG int i = 0; i < N; i++) A[i] = B[i] = (complex) {0, 0};

			for(RG int i = 0; i < n; i++)

				A[i] = (complex) {(C[i] == DNA[p]) ? 1. : 0., 0};

			for(RG int i = 0; i < m; i++)

				B[i] = (complex) {(S[i] == DNA[p]) ? 1. : 0., 0};

			FFT<1>(A); FFT<1>(B);

			for(RG int i = 0; i < N; i++) A[i] = A[i] * B[i];

			FFT<-1>(A);

			for(RG int i = m - 1; i < n; i++) ans[i] += (int) (A[i].x / N + .5);

		}

		int cnt = 0;

		for(RG int i = m - 1; i < n; i++) if(ans[i] + 3 >= m) ++cnt;

		printf("%d\n", cnt);

	}

	return 0;

}

巴特西

【TJOI2017】DNA

题面

题解

代码

最新文章

热门文章