fork download 
  1.  
  2. #include <cstring>
  3. #include <cstdio>
  4.  
  5. using namespace std;
  6.  
  7. const int base = 13331, Q1 = 1000000007, Q2 = 1000000009;
  8.  
  9. int hash1[1000001], hash2[1000001], power1[1000001], power2[1000001];
  10. char str[1000001];
  11.  
  12. bool check(int a, int b, int l) {
  13. 	int t1 = ((hash1[a+l] - (long long)hash1[a] * power1[l]) % Q1 + Q1) % Q1;
  14. 	int t2 = ((hash1[b+l] - (long long)hash1[b] * power1[l]) % Q1 + Q1) % Q1;
  15. 	if (t1 != t2) return false;
  16. 	int t3 = ((hash2[a+l] - (long long)hash2[a] * power2[l]) % Q2 + Q2) % Q2;
  17. 	int t4 = ((hash2[b+l] - (long long)hash2[b] * power2[l]) % Q2 + Q2) % Q2;
  18. 	if (t3 != t4) return false;
  19. 	return true;
  20. }
  21.  
  22. int main() {
  23. 	int n;
  24. 	scanf("%d%s", &n, str);
  25. 	hash1[0] = hash2[0] = 0;
  26. 	for (int i = 0; i < n; i ++) {
  27. 		hash1[i+1] = ((long long)hash1[i] * base + str[i]) % Q1;
  28. 		hash2[i+1] = ((long long)hash2[i] * base + str[i]) % Q2;
  29. 	}
  30. 	power1[0] = power2[0] = 1;
  31. 	for (int i = 1; i <= n; i ++) {
  32. 		power1[i] = (long long)power1[i-1] * base % Q1;
  33. 		power2[i] = (long long)power2[i-1] * base % Q2;
  34. 	}
  35.  
  36. 	int ans = 0;
  37. 	for (int i = n / 2 - 1, j = 0; i >= 0; i --) {
  38. 		j += 2;
  39. 		while (j >= 0 && (i + j > n / 2 || ! check(i, n - i - j, j))) j --;
  40. 		if (check(0, n - i, i) && i + j > ans) ans = i + j;
  41. 	}
  42. 	printf("%d\n", ans);
  43.  
  44. 	return 0;
  45. }
  46.  
Success #stdin #stdout 0.02s 19328KB
comments (?)
stdin 
15
ababbabababbaab
stdout 
6
https://ideone.com/uoc4D
language:
C++ (gcc 8.3)
created:
14 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!