Advertisement
ismaeil

B- Baby name

Sep 2nd, 2020
128
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.99 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. string Read(){
  5.     const int MaxN = 2e5 + 5e2;
  6.     static char Buff[MaxN];
  7.     scanf("\n%s" ,Buff);
  8.     return Buff;
  9. }
  10.  
  11. void CountSort(vector< int > &SA ,vector< int > &RA ,int k ,int n ,int N = 350){
  12.     vector< int > c(N ,0);
  13.     vector< int > tempSA(n);
  14.  
  15.     for(int i = 0 ; i < n ; i++)
  16.         c[ (i + k >= n) ? 0 : RA[i + k] ] ++;
  17.  
  18.     for(int i = 0, sum = 0 ; i < N ; i++){
  19.         int t = c[i];
  20.         c[i]  = sum;
  21.         sum += t;
  22.     }
  23.     for(int i = 0 ; i < n ; i++)
  24.         tempSA[ c[ ((SA[i] + k) < n) ? RA[ SA[i] + k ] : 0] ++ ] = SA[i];
  25.  
  26.     for(int i = 0 ; i < n ; i++) SA[i] = tempSA[i];
  27. }
  28.  
  29. vector< int > ConstructSA(string &s ,int n){
  30.     int r = 0;
  31.     vector< int > tempRA(n);
  32.     vector< int > SA(n) ,RA(n);
  33.  
  34.     for(int i = 0 ; i < n ; i++) RA[i] = (int)s[i];
  35.     for(int i = 0 ; i < n ; i++) SA[i] = i;
  36.  
  37.     for(int k = 1 ; k < n && (RA[ SA[n - 1] ] != n - 1) ; k <<= 1){
  38.         CountSort(SA ,RA ,k ,n);
  39.         CountSort(SA ,RA ,0 ,n);
  40.  
  41.         tempRA[ SA[0] ] = r = 0;
  42.         for(int i = 1 ; i < n ; i++) tempRA[ SA[i] ] =
  43.             (RA[ SA[i] ] == RA[ SA[i - 1] ] && RA[ SA[i] + k ] == RA[ SA[i - 1] + k ]) ? r : ++r;
  44.         for(int i = 0 ; i < n ; i++) RA[i] = tempRA[i];
  45.     }
  46.  
  47.     return SA;
  48. }
  49.  
  50. int main() {
  51.     string F = Read() + '$';
  52.     string M = Read() + '$';
  53.  
  54.     int n = (int)F.size();
  55.     int m = (int)M.size();
  56.  
  57.     vector< int > SuffF = ConstructSA(F ,n);
  58.     vector< int > SuffM = ConstructSA(M ,m);
  59.  
  60.     string mxF ,mxM;
  61.     for(int i = SuffF[n - 1] ; i < n ; i++) mxF += F[i];
  62.     for(int i = SuffM[m - 1] ; i < m ; i++) mxM += M[i];
  63.  
  64.  
  65.     bool flag = false;
  66.     for(auto i : mxF){
  67.         if( flag ) {
  68.             if( i < mxM[0] ) break;
  69.             if( i != '$' ) printf("%c" ,i);
  70.         } else {
  71.             if( i != '$' ) printf("%c" ,i);
  72.             flag = true;
  73.         }
  74.     }
  75.     for(auto i : mxM)
  76.         if( i != '$' ) printf("%c" ,i);
  77.     return 0;
  78. }
  79.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement