fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #include <climits>
  3. #define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
  4. #define srep(i, begin, end) for (__typeof(end) i = begin; i != end; i++)
  5. #define si(x) int x = scanInt();
  6. #define sll(x) LL x = scanLong();
  7. #define sci(x) int x; scanf("%d", &x);
  8. #define scll(x) LL x; scanf("%lld", &x);
  9. #define pi(x) printf("%d ", x)
  10. #define pll(x) printf("%lld ", x)
  11. #define ps(x) printf("%s", x)
  12. #define nl printf("\n")
  13. #define clr(a) memset(a, 0, sizeof(a))
  14. using namespace std;
  15. typedef unsigned int UI; // 32 bit integer
  16. typedef long int LI; // 32 bit integer
  17. typedef unsigned long int ULI; // 32 bit unsigned integer
  18. typedef long long int LL; // 64 bit integer
  19. typedef unsigned long long int  ULL; // 64 bit unsigned integer
  20. typedef long double LD;
  21. typedef vector<int> VI;
  22. typedef vector<LL> VLL;
  23. typedef pair<int, int> PII;
  24. typedef pair<LL, LL> PLL;
  25. LL mod = 1e9+7;
  26.  
  27. /* Fast I/O */
  28. inline int scanInt() {
  29. 	int n = 0;
  30. 	char ch = getchar();
  31. 	int sign = 1;
  32. 	while(ch < '0' || ch > '9') {
  33. 		if(ch == '-')	sign = -1;
  34. 		ch = getchar();
  35. 	}
  36. 	while(ch >= '0' && ch <= '9') {
  37. 		n = (n<<1)+(n<<3)+(int)(ch-'0');
  38. 		ch = getchar();
  39. 	}
  40. 	return n*sign;
  41. }
  42.  
  43. inline LL scanLong() {
  44. 	LL n = 0;
  45. 	char ch = getchar();
  46. 	LL sign = 1;
  47. 	while(ch < '0' || ch > '9') {
  48. 		if(ch == '-')	sign = -1;
  49. 		ch = getchar();
  50. 	}
  51. 	while(ch >= '0' && ch <= '9') {
  52. 		n = (n<<1)+(n<<3)+(LL)(ch-'0');
  53. 		ch = getchar();
  54. 	}
  55. 	return n*sign;
  56. }
  57.  
  58. const LL MAXN = 1010;
  59. const LL MAXLG = 10;
  60. string s;
  61. LL SA[MAXN], HP[MAXLG][MAXN], LCP[MAXN], N;
  62. // HP [i] [j]	denotes rank of suffix starting at j sorted according to first 2^i characters.
  63. // If first 2^i characters are same then their rank is same in HP[i].
  64.  
  65. struct entry{
  66. 	LL rank, next_rank, index;
  67. 	bool operator < (entry &oth) {
  68. 		if(rank == oth.rank) {
  69. 			if(next_rank == oth.next_rank)	return index < oth.index;
  70. 			return next_rank < oth.next_rank;
  71. 		}
  72. 		return rank < oth.rank;
  73. 	}
  74. } L[MAXN];
  75.  
  76. void construct() {
  77. 	rep(i, 0, N)	HP[0][i] = (LL)s[i];
  78. 	LL step = 1, cnt = 1;
  79. 	while(cnt < N) {
  80. 		rep(i, 0, N) {
  81. 			L[i].index = i;
  82. 			L[i].rank = HP[step-1][i];
  83. 			L[i].next_rank = (i + cnt < N) ? HP[step-1][i+cnt] : -1;
  84. 		}
  85. 		sort(L, L+N);
  86. 		LL r = 0;
  87. 		rep(i, 0, N) {
  88. 			if(i > 0 && L[i].rank == L[i-1].rank && L[i].next_rank == L[i-1].next_rank)
  89. 				HP[step][L[i].index] = HP[step][L[i-1].index];
  90. 			else
  91. 				HP[step][L[i].index] = r++;
  92. 		}
  93. 		step++;
  94. 		cnt <<= 1;
  95. 	}
  96. 	rep(i, 0, N)	SA[HP[step-1][i]] = i;
  97. 	rep(i, 0, N) {
  98. 		if(i == 0)	LCP[i] = 0;
  99. 		else {
  100. 			LL p = SA[i], q = SA[i-1];
  101. 			LCP[i] = 0;
  102. 			rep(x, step, 0) {
  103. 				if(HP[x][p] == HP[x][q] && p < N && q < N) {	
  104. 					LCP[i] += (((LL)1)<<x);
  105. 					p += (((LL)1)<<x);
  106. 					q += (((LL)1)<<x);
  107. 				}
  108. 			}
  109. 		}
  110. 	}
  111. }
  112.  
  113.  
  114. int main() {
  115. #ifndef ONLINE_JUDGE
  116. 	freopen("inp.txt", "r", stdin);
  117. #endif
  118. 	sll(t);
  119. 	while(t-->0) {
  120. 		// write your code here...
  121. 		cin >> s;
  122. 		N = s.size();
  123. 		construct();
  124. 		rep(i, 0, N)	pll(SA[i]); nl;
  125. 		LL ans = N*(N+1)/2;
  126. 		rep(i, 0, N)	ans -= LCP[i];
  127. 		pll(ans); nl;
  128. 	}
  129. }
  130.  
Success #stdin #stdout 0s 15360KB
comments (?)
stdin
copy 
2
ASDFGH
ABABAB
stdout
copy 
0 2 3 4 5 1 
21 
4 2 0 5 3 1 
11
https://ideone.com/GN888y
language:
C++14 (gcc 8.3)
created:
6 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!