fork download
copy 
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <string>
  4. #include <vector>
  5. using namespace std;
  6. const int Hash = 10007;
  7. int n, m, g[4], f[222];
  8. char P[1000005], Q[105];
  9. vector <string> h[Hash];
  10. int main() {
  11. 	int T;
  12. 	f['A'] = 0; f['C'] = 1; f['G'] = 2; f['T'] = 3;
  13. 	for (scanf("%d", &T); T--;) {
  14. 		scanf("%d%d\n", &n, &m);
  15. 		gets(P); gets(Q);
  16. 		for (int i = 0; i < 4; i++) {
  17. 			g[i] = i;
  18. 			for (int j = 0; j < m - 1; j++) g[i] = (g[i] * 4) % Hash;
  19. 		}
  20. 		vector <string> v;
  21. 		for (int i = 0; i <= m; i++) {
  22. 			for (int j = i; j <= m; j++) {
  23. 				string a, b, c, s;
  24. 				a = b = c = "";
  25. 				for (int k = 0; k < m; k++) {
  26. 					if (k < i) a += Q[k];
  27. 					else if (k < j) b += Q[k];
  28. 					else c += Q[k];
  29. 				}
  30. 				reverse(b.begin(), b.end());
  31. 				s = a + b + c;
  32. 				v.push_back(s);
  33. 			}
  34. 		}
  35. 		sort(v.begin(), v.end());
  36. 		int vn = v.size(), Sn;
  37. 		vector <string> S;
  38. 		string now = "";
  39. 		for (int i = 0; i < vn; i++) {
  40. 			if (now != v[i]) {
  41. 				now = v[i];
  42. 				S.push_back(now);
  43. 			}
  44. 		}
  45. 		Sn = S.size();
  46. 		int val = 0, cur;
  47. 		for (int i = 0; i < Sn; i++) {
  48. 			val = 0;
  49. 			for (int j = 0; j < m; j++) {
  50. 				cur = f[S[i][j]];
  51. 				val = (val * 4 + cur) % Hash;
  52. 			}
  53. 			h[val].push_back(S[i]);
  54. 		}
  55. 		val = 0;
  56. 		for (int i = 0; i < m; i++) {
  57. 			cur = f[P[i]];
  58. 			val = (val * 4 + cur) % Hash;
  59. 		}
  60. 		int res = 0, k;
  61. 		for (int i = m - 1; i < n; i++) {
  62. 			if (h[val].size() >= 1) {
  63. 				for (int j = 0; j < h[val].size(); j++) {
  64. 					for (k = 0; k < m; k++) if (P[i - m + 1 + k] != h[val][j][k]) break;
  65. 					if (k == m) {
  66. 						res++;
  67. 						break;
  68. 					}
  69. 				}
  70. 			}
  71. 			if (i < n - 1) {
  72. 				val = (val - g[f[P[i - m + 1]]] + Hash);
  73. 				val = (val * 4 + f[P[i + 1]]) % Hash;
  74. 			}
  75. 		}
  76. 		printf("%d\n", res);
  77. 		for (int i = 0; i < Hash; i++) h[i].clear();
  78. 	}
  79. }
Success #stdin #stdout 0s 4576KB
comments (?)
stdin
copy 
2
6 4
ATGGAT
AGGT
6 4
ATGGAT
AGCT
stdout
copy 
3
0
https://ideone.com/wwy6zW
language:
C++14 (gcc 8.3)
created:
9 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!