Saleh127

UVA 1223 / Suffix array_LCP

May 18th, 2022 (edited)
332
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. /***
  3.  created: 2022-05-18-17.08.41
  4. ***/
  5.  
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8. #define ll long long
  9. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  10. #define get_lost_idiot return 0
  11. #define nl '\n'
  12.  
  13. struct suf
  14. {
  15.     ll in;
  16.     ll rank[2];
  17.     ll lcp;
  18. } ;
  19.  
  20. suf suffix[1000002];
  21.  
  22. bool cmp(suf a,suf b)
  23. {
  24.     if(a.rank[0]==b.rank[0])
  25.     {
  26.         return a.rank[1]<b.rank[1];
  27.     }
  28.  
  29.     return a.rank[0]<b.rank[0];
  30. }
  31.  
  32. void suffixarray(string a,ll n)
  33. {
  34.  
  35.     ll i,j,k,l;
  36.  
  37.     for(i=0; i<n; i++)
  38.     {
  39.         suffix[i].in=i;
  40.         suffix[i].rank[0]=a[i]-'a';
  41.         suffix[i].rank[1]=(i+1<n)?(a[i+1]-'a'):-1;
  42.     }
  43.  
  44.     sort(suffix,suffix+n,cmp);
  45.  
  46.     ll index[n+2];
  47.  
  48.     for(ll k=4; k<2*n; k*=2)
  49.     {
  50.         ll rank = 0;
  51.         ll p_rank=suffix[0].rank[0];
  52.         suffix[0].rank[0]=rank;
  53.         index[suffix[0].in]=0;
  54.  
  55.         for(i=1; i<n; i++)
  56.         {
  57.             if(suffix[i].rank[0]==p_rank && suffix[i].rank[1]==suffix[i-1].rank[1])
  58.             {
  59.                 p_rank=suffix[i].rank[0];
  60.                 suffix[i].rank[0]=rank;
  61.             }
  62.             else
  63.             {
  64.                 p_rank=suffix[i].rank[0];
  65.                 suffix[i].rank[0]=++rank;
  66.             }
  67.             index[suffix[i].in]=i;
  68.         }
  69.         for(i=0; i<n; i++)
  70.         {
  71.             ll n_ind=suffix[i].in + k/2;
  72.             suffix[i].rank[1]=(n_ind<n)?suffix[index[n_ind]].rank[0]:-1;
  73.         }
  74.  
  75.         sort(suffix,suffix+n,cmp);
  76.  
  77.     }
  78. }
  79.  
  80. void lcpfind(string a,ll n)
  81. {
  82.     ll rank[n+4]= {0};
  83.  
  84.     ll i,j,k,l;
  85.  
  86.     for(i=0; i<n; i++)
  87.     {
  88.         rank[suffix[i].in]=i;
  89.         suffix[i].lcp=0;
  90.     }
  91.  
  92.     k=0;
  93.  
  94.     for(i=0; i<n; i++)
  95.     {
  96.         if(rank[i])
  97.         {
  98.             j=suffix[rank[i]-1].in;
  99.             while(a[i+k]==a[k+j]) k++;
  100.  
  101.             suffix[rank[i]].lcp=k;
  102.             if(k>0) k--;
  103.         }
  104.     }
  105. }
  106.  
  107.  
  108. int main()
  109. {
  110.     ios_base::sync_with_stdio(0);
  111.     cin.tie(0);
  112.     cout.tie(0);
  113.  
  114.     test
  115.     {
  116.         //longest substring appears>=2
  117.  
  118.         string a;
  119.  
  120.         cin>>a;
  121.  
  122.         ll n=a.size(),mx=0;
  123.  
  124.         suffixarray(a,n);
  125.  
  126.         lcpfind(a,n);
  127.  
  128.         for(ll i=0;i<n;i++)
  129.         {
  130.             mx=max(mx,suffix[i].lcp);
  131.         }
  132.  
  133.         cout<<mx<<nl;
  134.     }
  135.  
  136.  
  137.  
  138.     get_lost_idiot;
  139. }
  140.  
  141.  
  142.  
RAW Paste Data Copied