fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include <complex>
  3.  
  4. #define Write freopen("out.txt","w",stdout)
  5. #define Read freopen("in.txt","r",stdin)
  6.  
  7. #define si(a)           scanf("%d",&a)
  8. #define sii(a,b)        scanf("%d %d",&a,&b)
  9. #define siii(a,b,c)     scanf("%d %d %d",&a,&b,&c)
  10.  
  11. #define sl(a)           scanf("%lld",&a)
  12. #define sll(a,b)        scanf("%lld %lld",&a,&b)
  13. #define slll(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
  14.  
  15. #define m_p make_pair
  16. #define ll long long
  17.  
  18. #define lim 10000000
  19. #define mod 100007
  20. #define mx 100004
  21. using namespace std;
  22. #define MAX_N 200005 // second approach: O(n log n)
  23. string T;
  24. int n; // the length of input string
  25.  
  26. int RA[MAX_N], tempRA[MAX_N]; // rank array and temporary rank array
  27. int SA[MAX_N], tempSA[MAX_N]; // suffix array and temporary suffix array
  28.  
  29. int c[MAX_N]; // for counting/radix sort
  30.  
  31. void countingSort(int k)   // O(n)
  32. {
  33.  
  34.     int i, sum, maxi = max(300, n); // up to 255 ASCII chars or length of n
  35.     memset(c, 0, sizeof c); // clear frequency table
  36.  
  37.     for (i = 0; i < n; i++)  // count the frequency of each integer rank
  38.     {
  39.         c[i + k < n ? RA[i + k] : 0]++;
  40.     }
  41.  
  42.     for (i = sum = 0; i < maxi; i++)
  43.     {
  44.         int t = c[i];
  45.         c[i] = sum;
  46.         sum += t;
  47.     }
  48.     for (i = 0; i < n; i++)  // shuffle the suffix array if necessary
  49.     {
  50.         tempSA[c[SA[i]+k < n ? RA[SA[i]+k] : 0]++] = SA[i];
  51.     }
  52.     for (i = 0; i < n; i++)  // update the suffix array SA
  53.     {
  54.         SA[i] = tempSA[i];
  55.     }
  56. }
  57.  
  58. void suffixarray()   // this version can go up to 100000 characters
  59. {
  60.     n=T.size();
  61.     int i, k, r;
  62.     for (i = 0; i < n; i++) RA[i] = T[i]; // initial rankings
  63.     for (i = 0; i < n; i++) SA[i] = i; //initial SA: {0, 1, 2, ..., n-1}
  64.  
  65.     for (k = 1; k < n; k <<= 1)   // repeat sorting process log n times
  66.     {
  67.         countingSort(k); //actually radix sort:sort based on the second item
  68.         countingSort(0); // then (stable) sort based on the first item
  69.  
  70.         tempRA[SA[0]] = r = 0; // re-ranking; start from rank r = 0
  71.  
  72.         // compare adjacent suffixes
  73.         for (i = 1; i < n; i++)
  74.         {
  75.             // if same pair => same rank r; otherwise,increase r
  76.             tempRA[SA[i]] = (RA[SA[i]] == RA[SA[i-1]] && RA[SA[i]+k] == RA[SA[i-1]+k]) ? r : ++r;
  77.         }
  78.  
  79.         for (i = 0; i < n; i++) // update the rank array RA
  80.         {
  81.             RA[i] = tempRA[i];
  82.         }
  83.  
  84.         if (RA[SA[n-1]] == n-1) break; // nice optimization trick
  85.     }
  86. }
  87. int main()
  88. {
  89.  
  90.     cin>>T;
  91.     int cnt=0;
  92.     for(int i=0;i<T.size();i++)
  93.     {
  94.         if(T[i]==T[0]) cnt++;
  95.     }
  96.     if(cnt==T.size()){
  97.         cout<<"0"<<endl;
  98.         return 0;
  99.     }
  100.     int len=T.size();
  101.     T=T+T;
  102.     T+="$";
  103.     suffixarray();
  104.  
  105.  
  106.     for(int i=0;i<T.size()-1;i++)
  107.     {
  108.      if(SA[i]<len){
  109.         cout<<SA[i]<<endl;
  110.         return 0;
  111.      }
  112.  
  113.  
  114.     }
  115.   ///cout<<ans<<endl;
  116.  
  117. }
  118.  
  119.  
  120.  
  121.  
  122.  
Success #stdin #stdout 0s 19144KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/QHcYhW
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!