fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int p = 31; 
  12. const int MOD[2] = {(int)1e9 + 2277, (int)1e9 + 9277}; 
  13. const int N = 1e5 + 5; 
  14.  
  15. int n; 
  16. string s;  
  17. int p_pow[2][N], h[2][N]; 
  18.  
  19. void precompute() {
  20. 	for (int i = 0; i <= 1; i++) {
  21. 		p_pow[i][0] = 1;  
  22. 		for (int j = 1; j <= n; j++) p_pow[i][j] = 1ll * p_pow[i][j - 1] * p % MOD[i];  
  23. 	}
  24.  
  25. 	for (int i = 0; i <= 1; i++) {
  26. 		h[i][0] = 0;  
  27. 		for (int j = 1; j <= n; j++) h[i][j] = (1ll * h[i][j - 1] * p + (s[j] - 'a' + 1)) % MOD[i]; 
  28. 	}
  29. }
  30.  
  31. ii getHash(int l, int r) {
  32. 	ii ans; 
  33. 	ans.first = (h[0][r] - 1ll * h[0][l - 1] * p_pow[0][r - l + 1] % MOD[0] + MOD[0]) % MOD[0]; 
  34. 	ans.second = (h[1][r] - 1ll * h[1][l - 1] * p_pow[1][r - l + 1] % MOD[1] + MOD[1]) % MOD[1]; 
  35. 	return ans; 
  36. }
  37.  
  38. // Trả về chỉ số bắt đầu của xâu con có độ dài len xuất hiện ít nhất 2 lần trong xâu s
  39. // Nếu không tồn tại xâu con nào thì trả về -1
  40. int check(int len) {
  41. 	vector<pair<ii, int>> hs;  
  42. 	for (int i = 1; i + len - 1 <= n; i++) {
  43. 		ii cur_h = getHash(i, i + len - 1);  
  44. 		hs.push_back(make_pair(cur_h, i)); 
  45. 	}
  46.  
  47. 	sort(hs.begin(), hs.end());   
  48.  
  49. 	for (int i = 1; i < hs.size(); i++) {
  50. 		if (hs[i].first == hs[i - 1].first) return hs[i].second; 
  51. 	}
  52.  
  53. 	return -1; 
  54. }
  55.  
  56. int main() {
  57. 	ios::sync_with_stdio(false); 
  58. 	cin.tie(nullptr); 	
  59. 	cin >> s; 
  60. 	n = s.size(); 
  61. 	s = ' ' + s;  
  62.  
  63. 	precompute();  
  64.  
  65. 	int l = 1, r = n; ii ans = {-1, -1}; 
  66.  
  67. 	while (l <= r) {
  68. 		int mid = (l + r) >> 1; 
  69. 		int pos = check(mid); 
  70.  
  71. 		if (pos != -1) {
  72. 			ans = {mid, pos};  
  73. 			l = mid + 1; 
  74. 		}
  75. 		else {
  76. 			r = mid - 1; 
  77. 		}
  78. 	}
  79.  
  80. 	if (ans.first == -1) {
  81. 		cout << -1 << '\n'; 
  82. 	}
  83. 	else {
  84. 		cout << s.substr(ans.second, ans.first) << '\n'; 
  85. 	}
  86. }
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
cabababc
stdout
copy 
abab
https://ideone.com/XkXDLG
language:
C++14 (gcc 8.3)
created:
333 days 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!