Advertisement
ismaeil

C. Sorting Substrings

Oct 10th, 2020 (edited)
148
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.06 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef pair<int, int> ii;
  5. #define S second
  6. #define F first
  7.  
  8. vector< vector< int > > Rank;
  9. map< ii , int > Cnt;
  10. vector< ii > Seg;
  11. string s;
  12. int n ,q;
  13.  
  14. inline string Read()
  15. {
  16.     const int N = 4e5+5;
  17.     static char Buff[N];
  18.     scanf("\n%s",Buff);
  19.     return Buff;
  20. }
  21.  
  22. void CountSort(vector< int > &SA ,vector< int > &RA ,int k ,int n)
  23. {
  24.     int N = max(300,n);
  25.     vector< int > Cnt(N,0);
  26.     vector< int > tempSA(n);
  27.  
  28.     for(int i = 0 ; i < n ; i++)
  29.         Cnt[ (i + k >= n) ? 0 : RA[i + k] ] ++;
  30.  
  31.     for(int i = 0, sum = 0 ; i < N ; i++)
  32.     {
  33.         int t  = Cnt[i];
  34.         Cnt[i] = sum;
  35.         sum   += t;
  36.     }
  37.  
  38.     for(int i = 0 ; i < n ; i++)
  39.         tempSA[ Cnt[ ((SA[i] + k) < n) ? RA[ SA[i] + k ] : 0] ++ ] = SA[i];
  40.  
  41.     SA = tempSA;
  42. }
  43.  
  44. void RadixSort(vector< int > &SA ,vector< int > &RA ,int s ,int f ,int n)
  45. {
  46.     CountSort(SA ,RA ,s ,n);
  47.     CountSort(SA ,RA ,f ,n);
  48. }
  49.  
  50. vector< vector< int > > ConstructSA(string &s ,int n)
  51. {
  52.     vector< vector< int > > Rank((int)log2(n) ,vector< int >(n));
  53.  
  54.     vector< int > tempRA(n ,0) ,RA(n ,0) ,SA(n ,0);
  55.  
  56.     for(int i = 0 ; i < n ; i++) RA[i] = (int)s[i];
  57.     for(int i = 0 ; i < n ; i++) SA[i] = i;
  58.  
  59.     for(int k = 1 ; k < n && (RA[ SA[n - 1] ] != n - 1) ; k <<= 1 )
  60.     {
  61.         RadixSort(SA ,RA ,k ,0 ,n);
  62.  
  63.         int r = tempRA[ SA[0] ] = 0;
  64.         for(int i = 1 ; i < n ; i++)
  65.         {
  66.             bool flagF = (RA[ SA[i] ] == RA[ SA[i - 1] ]);
  67.             bool flagS = (RA[ (SA[i] + k) >= n ? 0 : SA[i] + k ] ==
  68.                           RA[ (SA[i - 1] + k) >= n ? 0 : SA[i - 1] + k ]);
  69.  
  70.             tempRA[ SA[i] ] = (flagF && flagS) ? r : ++r;
  71.         }
  72.  
  73.  
  74.         Rank[ (int)log2(k) ] = RA = tempRA;
  75.     }
  76.  
  77.     return Rank;
  78. }
  79.  
  80. inline int Calc(ii a ,ii b){
  81.     int LenA = a.S - a.F + 1;
  82.     int LenB = b.S - b.F + 1;
  83.  
  84.     int Len = min(LenA ,LenB);
  85.     int Log = log2( Len );
  86.  
  87.     ii A = ii( Rank[Log][a.F] , Rank[Log][ a.S - (1 << Log) + 1 ] );
  88.     ii B = ii( Rank[Log][b.F] , Rank[Log][ b.S - (1 << Log) + 1 ] );
  89.  
  90.     if( A.F < B.F ) return +1;
  91.     if( A.F > B.F ) return -1;
  92.     if( A.S < B.S ) return +1;
  93.     if( A.S > B.S ) return -1;
  94.  
  95.     if( LenA < LenB ) return +1;
  96.     if( LenA > LenB ) return -1;
  97.  
  98.     return 0;
  99. }
  100.  
  101. inline bool Cmp(const ii &a ,const ii &b){
  102.     int Res = Calc(a ,b);
  103.  
  104.     if( Res == +1 ) return true;
  105.     if( Res == -1 ) return false;
  106.  
  107.     if( a.F < b.F ) return true;
  108.     if( a.F > b.F ) return false;
  109.     if( a.S < b.S ) return true;
  110.     if( a.S > b.S ) return false;
  111.  
  112.     return false;
  113. }
  114.  
  115. int main()
  116. {
  117.     n = (int)(s = Read() + ' ').size();
  118.  
  119.     scanf("%d" ,&q);
  120.     for(int i = 0 ; i < q ; i++)
  121.     {
  122.         int L;  scanf("%d" ,&L) ,L --;
  123.         int R;  scanf("%d" ,&R) ,R --;
  124.  
  125.         ii x = ii(L ,R);
  126.         if( Cnt[x] == 0 ) Seg.push_back(x);
  127.         Cnt[x] += 1;
  128.     }
  129.  
  130.     Rank = ConstructSA(s ,n);
  131.  
  132.     sort(Seg.begin() ,Seg.end() ,Cmp); cout << endl;
  133.  
  134.     for(auto i : Seg) while( Cnt[i]-- ) printf("%d %d\n" ,i.F + 1 ,i.S + 1);
  135. }
  136.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement