Advertisement
ismaeil

Suffix Array template

Sep 3rd, 2020
145
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.32 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. string s;
  5. int n;
  6.  
  7. string Read(){
  8.     const int MaxN = 4e5 + 5e2;
  9.     static char Buff[MaxN];
  10.     scanf("\n%s" ,Buff);
  11.     return Buff;
  12. }
  13.  
  14. inline string SubStr(string &Str ,int Start ,int Len = 1e9){
  15.     /// --- Give String + StartIdx (If You Want To The End Of String) --- ///
  16.     /// --- Give String + StartIdx + Len (If You Want Len Of SubStr) ---- ///
  17.  
  18.     string Res;
  19.  
  20.     int N = (int)Str.size();
  21.     Len   = max(0 ,Len);
  22.     Start = max(0 ,Start);
  23.  
  24.     for(int i = Start ; (i < N && i < Start + Len) ; i++)
  25.         Res += Str[i];
  26.     return Res;
  27. }
  28.  
  29. void CountSort(vector< int > &SA ,vector< int > &RA ,int k ,int n){
  30.     int N = max(300 ,n);
  31.     vector< int > Cnt(N ,0);
  32.     vector< int > tempSA(n);
  33.  
  34.     /// --- Count The Repetitions --- ///
  35.     for(int i = 0 ; i < n ; i++)
  36.         Cnt[ (i + k >= n) ? 0 : RA[i + k] ] ++;
  37.  
  38.     /// --- Find The Correct Index Of Each Repetition --- ///
  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.     /// --- Put Each Repetition In It's Right Place --- ///
  46.     for(int i = 0 ; i < n ; i++)
  47.         tempSA[ Cnt[ ((SA[i] + k) < n) ? RA[ SA[i] + k ] : 0] ++ ] = SA[i];
  48.  
  49.     /// --- UPD Suffix Array --- ///
  50.     SA = tempSA;
  51. }
  52.  
  53. void RadixSort(vector< int > &SA ,vector< int > &RA ,int s ,int f ,int n){
  54.     CountSort(SA ,RA ,s ,n); /// --- Sort By Second --- ///
  55.     CountSort(SA ,RA ,f ,n); /// --- Sort By First  --- ///
  56.  
  57.     /// --- Sort The Pair ii(F ,S) --- ///
  58. }
  59.  
  60. vector< int > ConstructSA(string &s ,int n){
  61.     vector< int > tempRA(n ,0);
  62.     vector< int > SA(n ,0) ,RA(n ,0);
  63.  
  64.     for(int i = 0 ; i < n ; i++) RA[i] = (int)s[i];
  65.     for(int i = 0 ; i < n ; i++) SA[i] = i;
  66.  
  67.     for(int k = 1 ; k < n && (RA[ SA[n - 1] ] != n - 1) ; k <<= 1 ){
  68.         /// --- Sort pairs (RA[i] ,RA[i + k]) --- ///
  69.         RadixSort(SA ,RA ,k ,0 ,n);
  70.  
  71.         /// --- Give New Ranks After Sorting --- ///
  72.         int r = tempRA[ SA[0] ] = 0;
  73.         for(int i = 1 ; i < n ; i++){
  74.             bool flagF = (RA[ SA[i] ] == RA[ SA[i - 1] ]);
  75.             bool flagS = (RA[ (SA[i] + k) >= n ? 0 : SA[i] + k ] ==
  76.                           RA[ (SA[i - 1] + k) >= n ? 0 : SA[i - 1] + k ]);
  77.             tempRA[ SA[i] ] = (flagF && flagS) ? r : ++r;
  78.         }
  79.  
  80.         /// --- UPD Rank Array --- ///
  81.         RA = tempRA;
  82.     }
  83.  
  84.     return SA;
  85. }
  86.  
  87. /// --- Find Str t in Str s --- ///
  88. bool Search(vector< int > &Suff ,string &s ,int n ,string &t ,int m){
  89.     bool Res = false;
  90.  
  91.     /// --- Binary Search The Suffixes --- ///
  92.     int L = 0 ,R = n - 1;
  93.     while( L <= R && !Res ){
  94.         int Mid = (L + R) >> 1;
  95.  
  96.         string SubSuffString = SubStr(s ,Suff[Mid] ,m);
  97.  
  98.              if( SubSuffString < t ) L = Mid + 1;
  99.         else if( SubSuffString > t ) R = Mid - 1;
  100.         else Res = true;
  101.     }
  102.  
  103.     return Res;
  104. }
  105.  
  106. /// --- Count Occurs Of Str t in Str s --- ///
  107. int CntOfOccInStr(vector< int > &Suff ,string &s ,int n ,string &t ,int m){
  108.  
  109.     /// --- Binary Search The Suffixes Get LowerBound --- ///
  110.     int OccF;{
  111.         int L = 0 ,R = n - 1;
  112.         while( L <= R ){
  113.             int Mid = (L + R) >> 1;
  114.  
  115.             string SubSuffString = SubStr(s ,Suff[Mid] ,m);
  116.  
  117.                  if( SubSuffString >= t ) R = Mid - 1;
  118.             else if( SubSuffString <  t ) L = Mid + 1;
  119.         }
  120.  
  121.         string  SubSuffString = SubStr(s ,Suff[L] ,m);
  122.         OccF = (SubSuffString == t) ? L : -1;
  123.     }
  124.  
  125.     /// --- Binary Search The Suffixes Get UpperBound --- ///
  126.     int OccL;{
  127.         int L = 0 ,R = n - 1;
  128.         while( L <= R ){
  129.             int Mid = (L + R) >> 1;
  130.  
  131.             string SubSuffString = SubStr(s ,Suff[Mid] ,m);
  132.  
  133.                  if( SubSuffString >  t ) R = Mid - 1;
  134.             else if( SubSuffString <= t ) L = Mid + 1;
  135.         }
  136.  
  137.         string  SubSuffString = SubStr(s ,Suff[R] ,m);
  138.         OccL = (SubSuffString == t) ? R : -2;
  139.     }
  140.  
  141.     int Cnt = OccL - OccF + 1;
  142.     /// --- Ans = Idx OF UpperBound - Idx Of LowerBound + 1 --- ///
  143.     return Cnt;
  144. }
  145.  
  146. int main() {
  147.     n = (int)(s = Read() + '$').size();
  148.  
  149.     vector< int > Suff = ConstructSA(s ,n);
  150.  
  151.     for(int i = 0 ; i < n ; i++ , puts("")){
  152.         printf("%d %d " ,i ,Suff[i]);
  153.         for(auto i : s.substr(Suff[i]))
  154.             printf("%c" ,i);
  155.     }
  156. }
  157.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement