Advertisement
ismaeil

C. Sorting Substrings

Dec 19th, 2020
185
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.68 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. vector< ii > Seg;
  10. string s;
  11. int n ,q;
  12.  
  13. void CountSort(vector< int > &SA ,vector< int > &RA ,int k ,int n)
  14. {
  15.     int N = max(333 ,n);
  16.     vector< int > Cnt(N ,0);
  17.     vector< int > tempSA(n);
  18.  
  19.     for(int i = 0 ; i < n ; i++)
  20.         Cnt[ ( (i + k) >= n) ? 0 : RA[i + k] ] ++;
  21.  
  22.     for(int i = 0, sum = 0 ; i < N ; i++)
  23.     {
  24.         int t  = Cnt[i];
  25.         Cnt[i] = sum;
  26.         sum   += t;
  27.     }
  28.  
  29.     for(int i = 0 ; i < n ; i++)
  30.         tempSA[ Cnt[ ((SA[i] + k) < n) ? RA[ SA[i] + k ] : 0] ++ ] = SA[i];
  31.  
  32.     SA = tempSA;
  33. }
  34.  
  35. void RadixSort(vector< int > &SA ,vector< int > &RA ,int s ,int f ,int n)
  36. {
  37.     CountSort(SA ,RA ,s ,n);
  38.     CountSort(SA ,RA ,f ,n);
  39. }
  40.  
  41. vector< vector< int > > ConstructSA(string &s ,int n)
  42. {
  43.     vector< vector< int > > Rank((int)log2(n) + 2 ,vector< int >(n ,0));
  44.  
  45.     vector< int > tempRA(n ,0) ,SA(n ,0);
  46.  
  47.     for(int i = 0 ; i < n ; i++) Rank[0][i] = (int)s[i];
  48.     for(int i = 0 ; i < n ; i++) SA[i] = i;
  49.  
  50.     for(int k = 1 ; k < n ; k <<= 1 )
  51.     {
  52.         int LogRa = log2(k);
  53.         RadixSort(SA ,Rank[ LogRa ] ,k ,0 ,n);
  54.  
  55.         int r = tempRA[ SA[0] ] = 0;
  56.         for(int i = 1 ; i < n ; i++)
  57.         {
  58.             bool flagF = (Rank[LogRa][ SA[i] ] == Rank[LogRa][ SA[i - 1] ]);
  59.             bool flagS = (Rank[LogRa][ ( (SA[i] + k) >= n ) ? 0 : (SA[i] + k) ] ==
  60.                           Rank[LogRa][ ( (SA[i - 1] + k) >= n ) ? 0 : (SA[i - 1] + k) ]);
  61.  
  62.             tempRA[ SA[i] ] = (flagF && flagS) ? r : (++r);
  63.         }
  64.  
  65.         Rank[LogRa] = tempRA;
  66.     }
  67.  
  68.     return Rank;
  69. }
  70.  
  71. inline int Calc(int i ,int j ,int Len ,int Log)
  72. {
  73.     ii a = ii( Rank[Log][i] , Rank[Log][ ( i + Len - (1 << Log) ) % n ]);
  74.     ii b = ii( Rank[Log][j] , Rank[Log][ ( j + Len - (1 << Log) ) % n ]);
  75.     return (a == b ? 0 : a < b ? -1 : 1);
  76. }
  77.  
  78. inline bool Cmp(const ii &a ,const ii &b){
  79.  
  80.     int LenA = a.S - a.F + 1;
  81.     int LenB = b.S - b.F + 1;
  82.     int Len  = min(LenA ,LenB);
  83.     int Log  = log2(Len);
  84.  
  85.     int Res = Calc(a.F ,b.F ,Len ,Log);
  86.  
  87.     if( Res == +1 ) return false;
  88.     if( Res == -1 ) return true;
  89.  
  90.     if( LenA > LenB ) return false;
  91.     if( LenA < LenB ) return true;
  92.  
  93.     return a < b;
  94. }
  95.  
  96. int main()
  97. {
  98.     cin >> s >> q;
  99.  
  100.     s += ' ';
  101.     n = s.size();
  102.     for(int i = 0 ; i < q ; i++)
  103.     {
  104.         int L;  cin >> L ,L --;
  105.         int R;  cin >> R ,R --;
  106.         Seg.push_back( ii(L ,R) );
  107.     }
  108.  
  109.     Rank = ConstructSA(s ,n);
  110.  
  111.     sort(Seg.begin() ,Seg.end() ,Cmp); cout << endl;
  112.  
  113.     for(auto i : Seg) cout << i.F + 1 << ' ' << i.S + 1 << endl;
  114. }
  115.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement