fork download
copy 
  1. #include<iostream>
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<vector>
  5. #include<algorithm>
  6. #define REP(i, n) for (int i = 0; i < (int)(n); ++i)
  7. using namespace std;
  8.  
  9. int a[1000004];
  10. char S[1000002];
  11. int N, gap;
  12. int sa[1000002], pos[1000002], tmp[1000002], lcp[1000002];
  13.  char s[100];
  14. bool myfunc(int i, int j)
  15. {
  16.   if (pos[i] != pos[j])
  17.     return pos[i] < pos[j];
  18.   i += gap;
  19.   j += gap;
  20.   return (i < N && j < N) ? pos[i] < pos[j] : i > j;
  21. }
  22. // Building suffix array.
  23. void SA()
  24. {
  25.   N = strlen(S);
  26.   for(int i=0;i<N;i++){
  27.     sa[i] = i;
  28.     pos[i] = S[i];
  29.   }
  30.   for (gap = 1;; gap *= 2)
  31.   {
  32.     sort(sa, sa + N, myfunc);
  33.     for(int i=0;i<N-1;i++){
  34.       tmp[i + 1] = tmp[i] + myfunc(sa[i], sa[i + 1]);
  35.     }
  36.     for(int i=0; i<N;i++)
  37.     {
  38.       pos[sa[i]] = tmp[i];
  39.     }
  40.     if (tmp[N - 1] == N - 1) break;
  41.   }
  42. }
  43. // Building LCP array.
  44. void LCP()
  45. {
  46.   for (int i = 0, k = 0; i < N; ++i) if (pos[i] != N - 1)
  47.   {
  48.     for (int j = sa[pos[i] + 1]; S[i + k] == S[j + k];)
  49.       ++k;
  50.     lcp[pos[i]] = k;
  51.     if(k)
  52.       --k;
  53.   }
  54. }
  55.  
  56. void solve()
  57. {
  58.   SA();
  59.   LCP();
  60.  
  61.   long long int ans = N;
  62.   ans = (ans*(ans+1))/2;
  63.   long long int k = 0;
  64.   for(int i=0;i<N;i++)
  65.   {
  66.     k+=lcp[pos[i]];
  67.   }
  68.  
  69.   ans = ans - k;
  70.   ans%=1000000009;
  71.   //printf("%lld\n",ans);
  72.  
  73. }
  74.  
  75.  
  76. int main()
  77. {
  78.   int t,n;
  79.   scanf("%d", &t);
  80.   while(t--)
  81.   {
  82.     int zz=0;
  83.  
  84.     scanf("%s",&S);
  85.   n=strlen(S);
  86.     if(n==1)
  87.     {
  88.       printf("0\n");
  89.       continue;
  90.     }
  91.  
  92.     solve();
  93.     for(int i=0;i<n;i++)
  94. 	cout<<sa[i]<<endl;
  95.   }
  96.   return 0;
  97. }
  98.  
Time limit exceeded #stdin #stdout 5s 23240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8UVnhS
language:
C++ 4.3.2 (gcc-4.3.2)
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!