fork download 
  1. /* Author haleyk10198 */
  2. /* 作者:  haleyk10198 */
  3. #include <bits/stdc++.h>
  4.  
  5. #define MOD 1000000007
  6. #define LINF (1LL<<60)
  7. #define INF 2147483647
  8. #define PI 3.1415926535897932384626433
  9. #define ll long long
  10. #define pii pair<int,int>
  11. #define mp(x,y) make_pair((x),(y))
  12. #define MAXN 262144
  13.  
  14. using namespace std;
  15.  
  16. string itos(int x){
  17. 	stringstream ss;
  18. 	ss << x;
  19. 	return ss.str();
  20. }
  21.  
  22. map<char, int> m1;
  23. const string gene = "ACGT";
  24. string s, t;
  25.  
  26. int n, m, k, rescnt;
  27.  
  28. vector<complex<double> > vs[4], vt[4];
  29.  
  30. void fft(vector<complex<double> > &x){
  31. 	int n = x.size();
  32. 	if(n == 1)
  33. 		return ;
  34. 	vector<complex<double> > v[2];
  35. 	for(int i = 0; i < n; i++)
  36. 		v[i%2].push_back(x[i]);
  37. 	for(int i = 0; i < 2; i++)
  38. 		fft(v[i]);
  39. 	for(int i = 0 ; i < n/2; i++){
  40. 		double ar = 2*PI*i/n;
  41. 		complex<double> a, b, now = complex<double>(cos(ar), sin(ar));
  42. 		a = v[0][i];
  43. 		b = now*v[1][i];
  44. 		x[i] = a+b;
  45. 		x[i+n/2] = a-b;
  46. 	}
  47. }
  48.  
  49. void ifft(vector<complex<double> > &x){
  50. 	int n = x.size();
  51. 	if(n == 1)
  52. 		return;
  53. 	vector<complex<double> > v[2];
  54. 	for(int i = 0; i < n; i++)
  55. 		v[i%2].push_back(x[i]);
  56. 	for(int i = 0; i < 2; i++)
  57. 		fft(v[i]);
  58. 	for(int i = 0 ; i < n/2; i++){
  59. 		double ar = -2*PI*i/n;
  60. 		complex<double> a, b, now = complex<double>(cos(ar), sin(ar));
  61. 		a = v[0][i];
  62. 		b = now*v[1][i];
  63. 		x[i] = a+b;
  64. 		x[i+n/2] = a-b;
  65. 	}
  66. 	for(auto &y: x)
  67. 		y /= n;
  68. }
  69.  
  70. int main(){
  71. 	//freopen("input.txt","r",stdin);
  72. 	//freopen("output.txt","w",stdout);
  73. 	ios_base::sync_with_stdio(false);
  74. 	for(auto x: gene){
  75. 		int sz = m1.size();
  76. 		m1[x] = sz;
  77. 	}
  78. 	cin >> n >> m >> k >> s >> t;
  79. 	{
  80. 		for(int i = 0; i < 4; i++)
  81. 			vs[i] = vector<complex<double> >(MAXN, 0);
  82. 		{
  83. 			vector<int> lst = vector<int>(4, -MOD);
  84. 			int st = MAXN-n;
  85. 			for(int i = 0; i < n; i++){
  86. 				lst[m1[s[i]]] = i;
  87. 				for(int j = 0; j < 4; j++)
  88. 					if(lst[j]+k >= i)
  89. 						vs[j][st+i] = 1;
  90. 			}
  91. 			lst = vector<int>(4, MOD);
  92. 			for(int i = n; i; ){
  93. 				--i;
  94. 				lst[m1[s[i]]] = i;
  95. 				for(int j = 0; j < 4; j++)
  96. 					if(lst[j]-k <= i)
  97. 						vs[j][st+i] = 1;
  98. 			}
  99. 			st = MAXN - m;
  100. 			for(int i = 0; i < 4; i++)
  101. 				vt[i] = vector<complex<double> >(MAXN, 0);
  102. 			for(int i = 0; i < m; i++)
  103. 				vt[m1[t[i]]][i+st] = 1;
  104. 		}
  105. 		for(int i = 0; i < 4; i++)
  106. 			reverse(vt[i].begin(), vt[i].end());
  107. 	}
  108. 	for(int i = 0; i < 4; i++){
  109. 		fft(vs[i]);
  110. 		fft(vt[i]);
  111. 		for(int j = 0; j < MAXN; j++)
  112. 			vs[i][j] *= vt[i][j];
  113. 		ifft(vs[i]);
  114. 	}
  115. 	for(int i = 0; i < MAXN; i++){
  116. 		int tt = 0;
  117. 		for(int j = 0; j < 4; j++)
  118. 			tt += round(vs[j][i].real());
  119. 		if(tt == m)
  120. 			rescnt++;
  121. 	}
  122. 	cout << rescnt << endl;
  123. 	return 0;
  124. }
  125.  
Success #stdin #stdout 3.31s 3592KB
comments (?)
stdin 
10 4 1
AGCAATTCAT
ACAT
stdout 
3
https://ideone.com/Sl8iQA
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!