fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef vector <int> vi;
  5. #define inf (int)1e9
  6.  
  7. #define maxn 1510
  8.  
  9. char T[maxn];
  10. int n, c[maxn];
  11. int SA[maxn], RA[maxn], tempRA[maxn], tempSA[maxn];
  12.  
  13. void countingSort(int k){
  14.     int i, sum, maxi = max(300, n);
  15.     memset(c, 0, sizeof c);
  16.     for(i=0; i<n; i++) c[i + k < n ? RA[i+k] : 0]++;
  17.     for(i = sum = 0; i < maxi; i++){
  18.         int t = c[i]; c[i] = sum; sum += t;
  19.     }
  20.     for(i=0; i<n; i++)
  21.         tempSA[c[SA[i]+k < n ? RA[SA[i]+k] : 0]++] = SA[i];
  22.     for(i=0; i<n; i++) SA[i] = tempSA[i];
  23. }
  24. void constructSA(){
  25.     int i, r, k;
  26.     for(i=0; i<n; i++) SA[i] = i, RA[i] = T[i];
  27.     for(k=1; k<n; k<<=1){
  28.         countingSort(k); countingSort(0);
  29.         tempRA[SA[0]] = r = 0;
  30.         for(i=1; i<n; i++)
  31.             tempRA[SA[i]] = (RA[SA[i]] == RA[SA[i-1]] && RA[SA[i]+k] == RA[SA[i-1]+k]) ? r : ++r;
  32.         for(i=0; i<n; i++) RA[i] = tempRA[i];
  33.         if(RA[SA[n-1]] == n-1) break;
  34.     }
  35. }
  36.  
  37. int main(){
  38.     ios_base::sync_with_stdio(false);
  39.     cin.tie(nullptr);
  40.     //freopen("in.txt", "r", stdin);
  41.     //freopen("out.txt", "w", stdout);
  42.     int tc; cin >> tc;
  43.     while(tc--){
  44.         cin >> T; n = strlen(T);
  45.         T[n++] = '$'; T[n] = '\0';
  46.         constructSA();
  47.         int cnt = 0;
  48.         for(int i=0; SA[1]+i < n - 1; i++)
  49.             cnt++;
  50.         for(int i=2; i<n; i++){
  51.             bool flag = true;
  52.             for(int j=0; SA[i] + j < n - 1; j++){
  53.                 if(SA[i-1] + j >= n - 1 || T[SA[i] + j] != T[SA[i-1] + j]) flag = false;
  54.                 if(!flag) cnt++;
  55.             }
  56.         }
  57.         cout << cnt << "\n";
  58.     }
  59.     return 0;
  60. }
Success #stdin #stdout 0s 15272KB
comments (?)
stdin
copy 
2
CCCCC
ABABA
stdout
copy 
5
9
https://ideone.com/MEQrkh
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!