fork(1) download
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <queue>
  5. #include <list>
  6. #include <climits>
  7. #include <string>
  8. #include <stack>
  9. #include <map>
  10. #include <set>
  11. #include <cmath>
  12. #include <cstdio>
  13. #include <cstring>
  14. #include <cstdlib>
  15. #include <sstream>
  16. #include <iomanip>
  17.  
  18. #define ALL(v) v.begin(), v.end()
  19. #define REP(i, a, b) for(int i = a; i < b; i++)
  20. #define REPD(i, a, b) for(int i = a; i > b; i--)
  21. #define REPLL(i, a, b) for(ll i = a; i < b; i++)
  22. #define FOR(i, a, b) for(int i = a; i <= b; i++)
  23. #define FORD(i, a, b) for(int i = a; i >= b; i--)
  24. #define FORLL(i, a, b) for(ll i = a; i <= b; i++)
  25. #define INF 1000000001
  26.  
  27. #define vit vector<int>::iterator
  28. #define sit set<int>::iterator
  29. #define vi vector<int>
  30. #define vpii vector<pii >
  31.  
  32. #define ll long long
  33. #define ld long double
  34.  
  35. #define PB push_back
  36. #define MP make_pair
  37. #define pii pair<int, int>
  38. #define pld pair<ld, ld>
  39. #define st first
  40. #define nd second
  41.  
  42. #define EPS 1e-9
  43. #define PI acos(-1.0)
  44. #define MAXN 10007
  45.  
  46. using namespace std;
  47.  
  48. int z, n, m, a, b;
  49.  
  50. /// suffix array in O(nlogn) and O(n) memory
  51. /// always false sign # at the end!
  52.  
  53. int temp_suf[MAXN];
  54. int lcp[MAXN];
  55. int suf[MAXN], ra[MAXN], c[MAXN];
  56. char t[MAXN];
  57.  
  58. void count_sort(int k, int n, int* suf) {
  59. int i, sum, maxi = max(300, n);
  60. memset(c, 0, sizeof c);
  61. REP(i, 0, n) c[i + k < n ? ra[i + k] : 0]++;
  62. for (i = sum = 0; i < maxi; i++) {
  63. int t = c[i];
  64. c[i] = sum;
  65. sum += t;
  66. }
  67. REP(i, 0, n) temp_suf[c[suf[i] + k < n ? ra[suf[i] + k] : 0]++] = suf[i];
  68. REP(i, 0, n) suf[i] = temp_suf[i];
  69. }
  70.  
  71. void suf_array(const char *t, int n, int* suf) {
  72. int k, r;
  73. REP(i, 0, n) {
  74. ra[i] = t[i];
  75. suf[i] = i;
  76. }
  77. for (k = 1; k < n; k <<= 1) {
  78. count_sort(k, n, suf);
  79. count_sort(0, n, suf);
  80. temp_suf[suf[0]] = r = 0;
  81. REP(i, 1, n) temp_suf[suf[i]] = (ra[suf[i]] == ra[suf[i - 1]] && ra[suf[i] + k] == ra[suf[i - 1] + k] ? r : ++r);
  82. REP(i, 0, n) ra[i] = temp_suf[i];
  83. }
  84. }
  85.  
  86. /// LCP in O(n)
  87.  
  88. int r[MAXN];
  89. void count_lcp(const char *t, int n, int *suf, int *lcp) {
  90. int l = 0;
  91. REP(i, 0, n) r[suf[i]] = i;
  92. REP(i, 0, n) {
  93. if(r[i] == n-1) continue;
  94. int m = suf[r[i]+1];
  95. while(l+i < n && l+m < n && t[l + i] == t[l + m]) l++;
  96. lcp[r[i]] = l;
  97. l = max(0, l-1);
  98. }
  99. }
  100.  
  101. int main()
  102. {
  103. scanf("%d", &z);
  104.  
  105. while(z--) {
  106. scanf("%s", t);
  107. n = strlen(t);
  108. t[n++] = '@'; t[n] = 0;
  109. suf_array(t, n, suf);
  110. count_lcp(t, n, suf, lcp);
  111. int ret = n*(n-1)/2;
  112. REP(i, 0, n-1) ret -= lcp[i];
  113. printf("%d\n", ret);
  114. }
  115.  
  116. return 0;
  117. }
  118.  
Success #stdin #stdout 0s 3588KB
stdin
3
AABB
CCCCC
ABABA
stdout
8
5
9