Advertisement
Saleh127

UVA 11512 / Suffix_Array_LCP

May 19th, 2022
712
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(i+k<n && k+j<n && 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.         string a;
  117.  
  118.         cin>>a;
  119.  
  120.         ll n=a.size(),mx=0,cnt=0,id,i,j,last=-1,ans=0;;
  121.  
  122.         suffixarray(a,n);
  123.  
  124.         lcpfind(a,n);
  125.  
  126.         for(i=n-1;i>=0;i--)
  127.         {
  128.             if(suffix[i].lcp==last) cnt++;
  129.             else cnt=2;
  130.  
  131.  
  132.             if(suffix[i].lcp && suffix[i].lcp>=mx)
  133.             {
  134.                 mx=suffix[i].lcp;
  135.                 id=suffix[i].in;
  136.                 ans=cnt;
  137.  
  138.             }
  139.             last=suffix[i].lcp;
  140.         }
  141.  
  142.         if(mx==0) cout<<"No repetitions found!"<<nl;
  143.         else
  144.         {
  145.             for(i=id,j=0;j<mx;i++,j++)
  146.             {
  147.                 cout<<a[i];
  148.             }
  149.             cout<<" "<<ans<<nl;
  150.         }
  151.  
  152.         // cout<<mx<<nl;
  153.     }
  154.  
  155.     get_lost_idiot;
  156. }
  157.  
  158.  
  159.  
Advertisement
RAW Paste Data Copied
Advertisement