fork download
copy 
  1. #include <algorithm>
  2. #include <string>
  3. #include <vector>
  4. #include <iostream>
  5. #include <cmath> 
  6.  
  7. using namespace std;
  8.  
  9. const int MAX = 1e9;
  10. const int PRIME = 1e9+7;
  11. typedef long long ll;
  12. void powers_of_two(int n, vector<int> &t){
  13. 	int x = 1;
  14. 	for(int i = 0; i < n; i++){
  15. 		t.push_back(x);
  16. 		x *= 2;
  17. 	}
  18. }
  19.  
  20. struct _tuple{
  21. 	int index;
  22. 	int first;
  23. 	int second;
  24. 	_tuple(int index):index(index) {
  25. 		first = -1;
  26. 		second = -1;
  27. 	}
  28. 	~_tuple(){ }
  29. };
  30. /**
  31.  *	longest common prefix of two suffixes starting at indexes i and j
  32.  *	P is defined as in suffix_array
  33.  * 	x initial string
  34.  */
  35.  
  36. const int d = 22;
  37.  
  38. vector<int> powers;
  39.  
  40.  
  41.  
  42. int LCP(int i, int j, vector<vector<int>> &P, const string &x){
  43. 	int n = x.length();
  44. 	if (i == j) return n-i;
  45. 	// if (n == 1) return 0;
  46. 	int nn = static_cast<int>(floor(log2(n)))+1; //next power of two from length of x
  47. 	int total = 0;
  48. 	for(int step = nn; step >= 0; step--){
  49. 		if (i >= n || j >= n) break;
  50. 		if (P[step][i] == P[step][j]){
  51. 			total += powers[step];
  52. 			i += powers[step];
  53. 			j += powers[step];
  54. 		}
  55. 	}
  56. 	return total;	
  57. }
  58.  
  59. /**
  60.  * @param P  preliminary result P[i][j] is the rank of suffix at index "j" as compared using first 2^i characters
  61.  * @param x  actual string
  62.  */
  63. void suffix_array(vector<vector<int>> &P, const string &x){
  64. 	int n = x.length();
  65. 	int nn = static_cast<int>(floor(log2(n)))+1 ; //next power of two from length of x
  66. 	P.resize(nn+1, vector<int>(n, -1));
  67. 	if (n == 1) {
  68. 		P[0][0] = 0;
  69. 		return;
  70. 	}
  71. 	vector<_tuple> L(n, _tuple(0));
  72. 	for(int j = 0; j < n; j++){
  73. 		P[0][j] = x[j]-'a';
  74. 	}
  75. 	for(int i = 1; i <= nn; i++){
  76. 		for(int j = 0; j < n; j++){
  77. 			L[j].index = j;
  78. 			L[j].first = P[i-1][j];
  79. 			if (j + powers[i-1] < n){
  80. 				L[j].second = P[i-1][j+powers[i-1]];
  81. 			}
  82. 			else L[j].second = -1;
  83. 		}
  84. 		sort(L.begin(), L.end(), [](const _tuple &a, const _tuple &b){
  85. 			return a.first < b.first || (a.first == b.first && a.second < b.second);
  86. 		});
  87. 		for(int j = 0; j < n; j++){
  88. 			if (j == 0){
  89. 				P[i][L[j].index] = 0;
  90. 			}
  91. 			else {
  92. 				if (L[j].first == L[j-1].first && L[j].second == L[j-1].second){
  93. 					P[i][L[j].index] = P[i][L[j-1].index];
  94. 				} else {
  95. 					P[i][L[j].index] = j;
  96. 				}
  97. 			}
  98. 		}
  99. 	}
  100. }
  101.  
  102.  
  103. int main(int argc, char const *argv[])
  104. {
  105. 	powers_of_two(d, powers);
  106. 	string x, orig;
  107. 	cin >> x;
  108. 	orig = x;
  109. 	reverse(x.begin(), x.end());
  110. 	vector<vector<int>> P;
  111. 	suffix_array(P, x);
  112. 	int ans = 0;
  113. 	for(int i = 1; i < x.length(); i++){
  114. 		if (LCP(0, i, P, x) >= i) ans = i;
  115. 	}
  116. 	cout << orig.substr(orig.length()-ans, ans) << endl;
  117. 	return 0;
  118. }
  119.  
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
banana
stdout
copy 
na
https://ideone.com/aJCAYG
language:
C++14 (gcc 8.3)
created:
7 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!