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. template<typename T>
  12. void maximize(T& a, const T& b) {
  13. 	if (a < b) a = b;  
  14. }
  15.  
  16. const int p = 31;  
  17. const int MOD = 1e9 + 9277; 
  18. const int N = 1e6 + 5; 
  19.  
  20. int n; 
  21. string s; 
  22. int p_pow[N], inv_p_pow[N]; 
  23. int h[N], rev_h[N]; 
  24.  
  25. int binpow(int a, int b) {
  26. 	int ans = 1; 
  27. 	for (; b > 0; b >>= 1) {
  28. 		if (b & 1) ans = 1ll * ans * a % MOD;  
  29. 		a = 1ll * a * a % MOD; 
  30. 	}
  31. 	return ans;
  32. }
  33.  
  34. void precompute() {
  35. 	p_pow[0] = 1; 
  36. 	for (int i = 1; i <= n; i++) {
  37. 		p_pow[i] = 1ll * p_pow[i - 1] * p % MOD; 
  38. 	}
  39.  
  40. 	inv_p_pow[n] = binpow(p_pow[n], MOD - 2); 
  41. 	for (int i = n - 1; i >= 0; i--) {
  42. 		inv_p_pow[i] = 1ll * inv_p_pow[i + 1] * p % MOD; 
  43. 	}
  44.  
  45. 	h[0] = rev_h[0] = 0;   
  46. 	for (int i = 1; i <= n; i++) {
  47. 		h[i] = (1ll * h[i - 1] * p + (s[i] - 'a' + 1)) % MOD; 
  48. 		rev_h[i] = (rev_h[i - 1] + 1ll * p_pow[i - 1] * (s[i] - 'a' + 1) % MOD) % MOD; 
  49. 	}
  50. }
  51.  
  52. int getHash(int l, int r) {
  53. 	return (h[r] - 1ll * h[l - 1] * p_pow[r - l + 1] % MOD + MOD) % MOD; 
  54. }
  55.  
  56. // Giá trị hash của xâu s[l..r] sau khi đảo ngược
  57. int getRevHash(int l, int r) {
  58. 	return 1ll * (rev_h[r] - rev_h[l - 1] + MOD) % MOD * inv_p_pow[l - 1] % MOD; 
  59. }
  60.  
  61. bool isPalin(int l, int r) {
  62. 	return (getHash(l, r) == getRevHash(l, r)); 
  63. }
  64.  
  65. // Với mỗi tâm đối xứng center thì tìm độ dài "bán kính" lớn nhất
  66. ii maxOddLength() {
  67. 	ii best = {0, 0};  
  68. 	for (int center = 1; center <= n; center++) {
  69. 		int l = 0, r = min(center - 1, n - center), ans = 0; 
  70. 		while (l <= r) {
  71. 			int mid = (l + r) >> 1; 
  72. 			if (isPalin(center - mid, center + mid)) {
  73. 				ans = mid;  
  74. 				l = mid + 1; 
  75. 			}
  76. 			else {
  77. 				r = mid - 1; 
  78. 			}
  79. 		}
  80. 		maximize(best, make_pair(2 * ans + 1, center - ans)); 
  81. 	}
  82. 	return best; 
  83. }
  84.  
  85. ii maxEvenLength() {
  86. 	ii best = {0, 0}; 
  87. 	for (int center = 1; center + 1 <= n; center++) {
  88. 		int l = 1, r = min(center, n - center), ans = 0;
  89. 		while (l <= r) {
  90. 			int mid = (l + r) >> 1;   
  91. 			if (isPalin(center - mid + 1, center + mid)) {
  92. 				ans = mid;  
  93. 				l = mid + 1; 
  94. 			}
  95. 			else {
  96. 				r = mid - 1; 
  97. 			}
  98. 		} 
  99. 		maximize(best, make_pair(2 * ans, center - ans + 1)); 
  100. 	}
  101. 	return best; 
  102. }
  103.  
  104. int main() {
  105. 	ios::sync_with_stdio(false); 
  106. 	cin.tie(nullptr); 	
  107. 	cin >> s; 
  108. 	n = s.size(); 
  109. 	s = ' ' + s;  
  110.  
  111. 	precompute();  
  112.  
  113. 	// ans.first = độ dài xâu con đối xứng dài nhất
  114. 	// ans.second = vị trí bắt đầu của nó trong xâu s
  115. 	ii ans = max(maxOddLength(), maxEvenLength()); 
  116.  
  117. 	string t = s.substr(ans.second, ans.first); 
  118. 	cout << t << '\n'; 
  119. }
Success #stdin #stdout 0.01s 9716KB
comments (?)
stdin
copy 
aybabtu
stdout
copy 
bab
https://ideone.com/3xW0NM
language:
C++14 (gcc 8.3)
created:
338 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!