fork(1) download
copy 
  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
comments (?)
stdin
copy 
3
AABB
CCCCC
ABABA
stdout
copy 
8
5
9
https://ideone.com/6zlXeV
language:
C++14 (gcc 8.3)
created:
10 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!