fork download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. typedef pair <int, int> pii;
  6. const int H[3] = { 100007, 28922, 912312 };
  7. int n, A[200005], g[26][200005][3];
  8. char S[200005];
  9. bool ok(int X) {
  10.   int v[3] = { 0, };
  11. 	for (int i = 1; i <= X; i++) for (int j = 0; j < 3; j++) v[j] = (v[j] * 26 + A[i]) % H[j];
  12. 	vector <pii> table[100007];
  13. 	pii cur;
  14. 	for (int i = X; i <= n; i++) {
  15. 		cur = make_pair(v[1], v[2]);
  16. 		for (int j = 0; j < table[v[0]].size(); j++) if (cur == table[v[0]][j]) return 1;
  17. 		if (i < n) {
  18. 			table[v[0]].push_back(cur);
  19. 			for (int j = 0; j < 3; j++) {
  20. 				v[j] = (v[j] - g[A[i - X + 1]][X][j] + H[j]) % H[j];
  21. 				v[j] = (v[j] * 26 + A[i + 1]) % H[j];
  22. 			}
  23. 		}
  24. 	}
  25. 	return 0;
  26. }
  27. int main() {
  28. 	scanf("%d\n", &n);
  29. 	gets(S + 1);
  30. 	for (int k = 0; k < 3; k++) {
  31. 		for (int i = 0; i < 26; i++) {
  32. 			g[i][1][k] = i;
  33. 			for (int j = 2; j <= n; j++) g[i][j][k] = (g[i][j-1][k] * 26) % H[k];
  34. 		}
  35. 	}
  36. 	for (int i = 1; i <= n; i++) A[i] = (S[i] - 'a');
  37. 	int low = 0, high = n - 1, res = 0, mid;
  38. 	while (low <= high) {
  39. 		mid = (low + high) / 2;
  40. 		if (ok(mid)) {
  41. 			if (res < mid) res = mid;
  42. 			low = mid + 1;
  43. 		}
  44. 		else high = mid - 1;
  45. 	}
  46. 	printf("%d", res);
  47. }
Success #stdin #stdout 0s 66432KB
comments (?)
stdin
copy 
11
sabcabcfabc
stdout
copy 
3
https://ideone.com/ou87GL
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!