Advertisement
ismaeil

C. Sorting Substrings

Oct 5th, 2020
154
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.85 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< ii > Seg;
  9. string s;
  10. int n ,q;
  11.  
  12. string Read(){
  13.     const int MaxN = 4e5 + 5e2;
  14.     static char Buff[MaxN];
  15.     scanf("\n%s" ,Buff);
  16.     return Buff;
  17. }
  18.  
  19. string SubStr(string &Str ,int Start ,int Len = 1e9){
  20.     string Res;
  21.  
  22.     int N = (int)Str.size();
  23.     Len   = max(0 ,Len);
  24.     Start = max(0 ,Start);
  25.  
  26.     for(int i = Start ; (i < N && i < Start + Len) ; i++)
  27.         Res += Str[i];
  28.     return Res;
  29. }
  30.  
  31. void CountSort(vector< int > &SA ,vector< int > &RA ,int k ,int n){
  32.     int N = max(300 ,n);
  33.     vector< int > Cnt(N ,0);
  34.     vector< int > tempSA(n);
  35.  
  36.     for(int i = 0 ; i < n ; i++)
  37.         Cnt[ (i + k >= n) ? 0 : RA[i + k] ] ++;
  38.  
  39.     for(int i = 0, sum = 0 ; i < N ; i++){
  40.         int t = Cnt[i];
  41.         Cnt[i] = sum;
  42.         sum += t;
  43.     }
  44.  
  45.     for(int i = 0 ; i < n ; i++)
  46.         tempSA[ Cnt[ ((SA[i] + k) < n) ? RA[ SA[i] + k ] : 0] ++ ] = SA[i];
  47.  
  48.     SA = tempSA;
  49. }
  50.  
  51. void RadixSort(vector< int > &SA ,vector< int > &RA ,int s ,int f ,int n){
  52.     CountSort(SA ,RA ,s ,n);
  53.     CountSort(SA ,RA ,f ,n);
  54. }
  55.  
  56. vector< int > ConstructSA(string &s ,int n){
  57.     vector< int > tempRA(n ,0);
  58.     vector< int > SA(n ,0) ,RA(n ,0);
  59.  
  60.     for(int i = 0 ; i < n ; i++) RA[i] = (int)s[i];
  61.     for(int i = 0 ; i < n ; i++) SA[i] = i;
  62.  
  63.     for(int k = 1 ; k < n && (RA[ SA[n - 1] ] != n - 1) ; k <<= 1 ){
  64.         RadixSort(SA ,RA ,k ,0 ,n);
  65.  
  66.         int r = tempRA[ SA[0] ] = 0;
  67.         for(int i = 1 ; i < n ; i++){
  68.             bool flagF = (RA[ SA[i] ] == RA[ SA[i - 1] ]);
  69.             bool flagS = (RA[ (SA[i] + k) >= n ? 0 : SA[i] + k ] ==
  70.                           RA[ (SA[i - 1] + k) >= n ? 0 : SA[i - 1] + k ]);
  71.             tempRA[ SA[i] ] = (flagF && flagS) ? r : ++r;
  72.         }
  73.  
  74.         RA = tempRA;
  75.     }
  76.  
  77.     return SA;
  78. }
  79.  
  80. vector< int > GetLCP(vector< int > &Suff ,string &s ,int n){
  81.     vector< int > PLCP(n);
  82.     vector< int > LCP(n);
  83.     vector< int > Phi(n);
  84.  
  85.     Phi[ Suff[0] ] = -1;
  86.     for(int i = 1 ; i < n ; i++) Phi[ Suff[i] ] = Suff[i - 1];
  87.  
  88.     for(int i = 0 ,Len = 0 ; i < n ; i ++){
  89.         if( Phi[i] != -1 ){
  90.             while( (i + Len < n) && (Phi[i] + Len < n)
  91.                   && (s[i + Len] == s[Phi[i] + Len]) )
  92.                     Len += 1;
  93.             PLCP[i] = Len;
  94.             Len = max(Len - 1 ,0);
  95.         } else PLCP[i] = 0;
  96.     }
  97.  
  98.     for(int i = 0 ; i < n ; i++) LCP[i] = PLCP[ Suff[i] ];
  99.     return LCP;
  100. }
  101.  
  102. int Search(vector< int > &Suff ,vector< int > &LCP ,vector< int > &Pos ,string &s ,int n ,int L ,int R) {
  103.     int Len = R - L + 1 ,Idx = Pos[L - 1];
  104.     while( LCP[Idx] >= Len ) Idx -= 1;
  105.     return Idx;
  106. }
  107.  
  108. inline bool Sorter(ii &a ,ii &b){
  109.     int LenA = a.S - a.F + 1;
  110.     int LenB = b.S - b.F + 1;
  111.  
  112.     if( LenA  < LenB ) return true;
  113.     if( LenA == LenB ){
  114.         if( a.F  < b.F ) return true;
  115.         if( a.F == b.F && a.S < b.S ) return true;
  116.     }
  117.  
  118.     return false;
  119. }
  120.  
  121. int main() {
  122.     n = (int)(s = Read() + ' ').size();
  123.  
  124.     scanf("%d" ,&q);             Seg.resize( q );
  125.     for(auto &i : Seg) scanf("%d%d" ,&i.F ,&i.S);
  126.  
  127.     vector< int > Suff = ConstructSA(s ,n);
  128.     vector< int > LCP = GetLCP(Suff ,s ,n);
  129.  
  130.     vector< int > Pos(n);
  131.     for(int i = 0 ; i < n ; i++) Pos[ Suff[i] ] = i;
  132.  
  133.     map< ii , pair<bool , int> > FirstOcc;
  134.     map<int , vector< ii > > Cnt;
  135.     for(auto i : Seg){
  136.             if( !FirstOcc[i].F ){
  137.                     FirstOcc[i].F = true;
  138.                     FirstOcc[i].S = Search(Suff ,LCP ,Pos ,s ,n ,i.F ,i.S);
  139.             }
  140.             Cnt[ FirstOcc[i].S ].push_back(i);
  141.     }
  142.  
  143.     vector< ii > Ans;
  144.     for(auto &i : Cnt){
  145.         sort(i.S.begin() ,i.S.end() ,Sorter);
  146.         for(auto j : i.S) Ans.push_back(j);
  147.     }
  148.  
  149.     for(auto i : Ans) printf("%d %d\n" ,i.F ,i.S);
  150.     return 0;
  151. }
  152.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement