fork download 
  1. #include<stdio.h>
  2. #include<vector>
  3. using namespace std;
  4. struct tri {int next[4];}node[500*500];
  5. int nn = 1;
  6. char A[515][515], B[515][515];
  7. vector<int>dep[515];
  8. int trans[256];
  9. int min(int a, int b) { if (a > b)return b; return a; }
  10. int max(int a, int b) { if (a > b)return a; return b; }
  11. int main() {
  12. 	int n, m, i, j, k;
  13. 	int ans = 1e9;
  14. 	trans['A'] = 0, trans['C'] = 1, trans['G'] = 2, trans['T'] = 3;
  15. 	scanf("%d%d", &n, &m);
  16. 	for (i = 0; i < n; i++) scanf("%s", A[i]);
  17. 	for (i = 0; i < n; i++) scanf("%s", B[i]);
  18. 	for (i = 0; i < m; i++) {
  19. 		node[1] = { {0,0,0,0} }, nn = 1;
  20. 		for (j = 0; j < n; j++) {
  21. 			int now = 1;
  22. 			for (k = i; k < m; k++) {
  23. 				if (!node[now].next[trans[A[j][k]]])
  24. 					node[now].next[trans[A[j][k]]] = ++nn, node[nn] = { {0,0,0,0} };
  25. 				now = node[now].next[trans[A[j][k]]];
  26. 			}
  27. 		}
  28. 		int res = 0;
  29. 		for (j = 0; j < n; j++) {
  30. 			int now = 1;
  31. 			int dep = 0;
  32. 			for (k = i; k < m; k++,dep++) {
  33. 				if (!node[now].next[trans[B[j][k]]])break;
  34. 				now = node[now].next[trans[B[j][k]]];
  35. 			}
  36. 			if (k == m)res = 1e9;
  37. 			res = max(res, dep + 1);
  38. 		}
  39. 		ans = min(ans, res);
  40. 	}
  41. 	printf("%d", ans);
  42. 	return 0;
  43. }
Success #stdin #stdout 0s 4532KB
comments (?)
stdin 
3 8
AATCCCAT
ACTTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT
stdout 
4
https://ideone.com/ou6CGJ
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!