fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define all(c) (c).begin(), (c).end()
  4. #define cnt(c, x) ((c).find(x) != (c).end())
  5. #define pb push_back
  6. #define FOR(i, a, n) for(int i = (a); i < (n); i++)
  7. #define REP(i, n) for(int i = 0; i < (n); i++)
  8. #define SZ(x) ((int) (x).size())
  9. #define mp(x,y) make_pair((x), (y))
  10. #define mp3(x,y,z) make_pair((x), make_pair( (y), (z)))
  11. #define foreach(C, i) for(auto i = (C).begin(); i != (C).end(); i++)
  12. #define xx first
  13. #define yy second
  14. #define clr clear()
  15. #define var(x) cout<< #x << " = "<<x<<"\n";
  16. #define print(x) for_each((x).begin(), (x).end(), [](auto n) { cout<<x<<" " })
  17. typedef int32_t i3;
  18. typedef int64_t i6;
  19. typedef vector<i3> vi;
  20. typedef pair<i3,i3> ii;
  21. typedef vector<pair<i3,i3> > vii;
  22.  
  23. class SuffixArray
  24. {
  25. 	public:
  26. 		string str;
  27. 		vector<array<int,3> > vec;
  28. 		vector<vector<int> > dp;
  29. 		vector<int> suff;
  30. 		SuffixArray(string st)
  31. 		{
  32. 			str = st + "$";
  33. 			vec = vector<array<int,3> >(SZ(str));
  34. 			dp = vector<vector<int> >(ceil(log2(SZ(str))) + 1, vector<int> (SZ(str),-1));
  35. 			suff = vector<int> (SZ(str)-1);
  36. 		}
  37. 		void construct()
  38. 		{
  39. 			vector<pair<string,int > > temp;
  40. 			REP(i, SZ(str))
  41. 				temp.pb(make_pair(str.substr(i,1), i));
  42. 			sort(all(temp));
  43. 			map<string,int> mp;
  44. 			int index = 0;
  45. 			foreach(temp, it)
  46. 			{
  47. 				string st = it->first;
  48. 				if (mp.count(st) == 0)
  49. 					mp[st] = index++;
  50. 			}
  51. 			foreach(temp, it)
  52. 				dp[0][it->second] = mp[it->first];
  53. 			int step = 0;
  54. 			for(step = 0; (1 << step) < SZ(str); step++)
  55. 			{
  56. 				for(int i = 0; i < SZ(str); i++)
  57. 				{
  58. 					if (i + (1 << step) < SZ(str))
  59. 						vec[i] = { dp[step][i], dp[step][i + (1 << step)], i };
  60. 					else
  61. 						vec[i] = { dp[step][i], -1, i };
  62. 				}
  63. 				sort(all(vec));
  64. 				index = 0;
  65. 				mp.clear();
  66. 				for(array<int,3>& arr : vec)
  67. 				{	
  68. 					string st2 = str.substr(arr[2], min(1 << (step+1), SZ(str) - arr[2] - 1));
  69. 					if (mp.find(st2) == mp.end())
  70. 						mp[st2] = index++;
  71. 				}
  72. 				for(array<int,3> & arr : vec)
  73. 				{
  74. 					string st2 = str.substr(arr[2], min(1 << (step+1), SZ(str) - arr[2] - 1));
  75. 					dp[step+1][arr[2]] = mp[st2];
  76. 				}
  77. 			}
  78. 			for(int i = 0; i < SZ(str)-1; i++)
  79. 				suff[i] = dp[step][i] - 1;
  80.  
  81. 		}
  82. };
  83. int main()
  84. {
  85. 	string str; cin >> str;
  86. 	SuffixArray suff(str);
  87. 	suff.construct();
  88. 	for(int num : suff.suff)
  89. 		cout << num << " ";
  90. 	cout << "\n";
  91. 	return (0);
  92. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
banana
stdout
copy 
3 2 5 1 4 0
https://ideone.com/VEHlld
language:
C++14 (gcc 8.3)
created:
8 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!