Advertisement
Saleh127

UVA 760 / Suffix Array

May 23rd, 2022
654
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2022-05-22-10.21.44
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10. #define nl '\n'
  11.  
  12. //O(nlgn)
  13. vector<int> sac(string s)
  14. {
  15.     s += '`';
  16.     int n = s.size();
  17.     const int A=28;
  18.     vector<int> p(n), c(n), cnt(max(n, A));
  19.     for (int i = 0; i < n; ++i) cnt[s[i]-'`']++;
  20.     for (int i = 1; i < A; ++i) cnt[i] += cnt[i-1];
  21.     for (int i = n-1; i >=0; --i) p[--cnt[s[i]-'`']] = i;
  22.     int rnk = 1;
  23.     for (int i = 1; i < n; ++i)
  24.     {
  25.         if(s[p[i]] != s[p[i-1]])  rnk++;
  26.         c[p[i]] = rnk-1;
  27.     }
  28.  
  29.     vector<int> pn(n), cn(n);
  30.     for (int k = 0; (1<<k) < n; ++k)
  31.     {
  32.         for (int i = 0; i < n; ++i)
  33.         {
  34.             pn[i] = p[i] - (1<<k);
  35.             if(pn[i] < 0) pn[i] += n;
  36.         }
  37.         fill(cnt.begin(), cnt.begin()+rnk, 0);
  38.         for (int i = 0; i < n; ++i) cnt[c[pn[i]]]++;
  39.         for (int i = 1; i < rnk; ++i) cnt[i] += cnt[i-1];
  40.         for (int i = n-1; i >= 0; --i) p[--cnt[c[pn[i]]]] = pn[i];
  41.  
  42.         cn[p[0]]=0;
  43.         rnk = 1;
  44.         for (int i = 1; i < n; ++i)
  45.         {
  46.             int x = p[i]+(1<<k), y = p[i-1]+(1<<k);
  47.             if(x >= n)  x -= n;
  48.             if(y >= n)  y -= n;
  49.             pair<int, int> cur = {c[p[i]], c[x]};
  50.             pair<int, int> prev = {c[p[i-1]], c[y]};
  51.             if(cur != prev) rnk++;
  52.             cn[p[i]] = rnk-1;
  53.         }
  54.         c.swap(cn);
  55.     }
  56.  
  57.     p.erase(p.begin());
  58.     return p;
  59. }
  60.  
  61. //kasai's alog :: O(n)
  62.  
  63. vector<int> LCP(string s, vector<int> p)
  64. {
  65.     int n = s.size();
  66.     vector<int> idx(n);
  67.     for (int i = 0; i < n; ++i) idx[p[i]] = i;
  68.     int k = 0;
  69.     vector<int> lcp(n-1);
  70.     for (int i = 0; i < n; ++i)
  71.     {
  72.         if(idx[i]==n-1)
  73.         {
  74.             k = 0;
  75.             continue;
  76.         }
  77.         int j = p[idx[i]+1];
  78.         while(i+k<n and j+k<n and s[i+k]==s[j+k]) k++;
  79.         lcp[idx[i]] = k;
  80.         if(k) k--;
  81.     }
  82.     return lcp;
  83. }
  84.  
  85. //unsigned long long int N_Different_Substrings(const vector<int> &suffixArray, const vector<int> &lcp) {
  86. //    unsigned long long int res = suffixArray[0];
  87. //    for (int i = 1; i < suffixArray.size(); i++) {
  88. //        res += suffixArray[i] - lcp[i - 1];
  89. //    }
  90. //    return res;
  91. //}
  92.  
  93.  
  94. int main()
  95. {
  96.     ios_base::sync_with_stdio(0);
  97.     cin.tie(0);
  98.     cout.tie(0);
  99.  
  100.  
  101.     string s, p,y;
  102.     ll tt=0;
  103.  
  104.     while(getline(cin,s))
  105.     {
  106.         getline(cin,p);
  107.  
  108.         y=s+'{'+p;
  109.  
  110.         vector<int>sa =sac(y);
  111.  
  112.         vector<int>lcp =LCP(y,sa);
  113.  
  114.         ll n,ans=0,in,i;
  115.  
  116.         n=s.size();
  117.  
  118.         for(i=0; i<sa.size()-1; i++)
  119.         {
  120.             if((sa[i]<n && sa[i+1]>n) || (sa[i]>n && sa[i+1]<n))
  121.             {
  122.                 if(lcp[i]>ans)
  123.                 {
  124.                     ans=lcp[i];
  125.                 }
  126.             }
  127.         }
  128.  
  129.         tt++;
  130.  
  131.         if(tt>=2) cout<<nl;
  132.  
  133.         set<string>z;
  134.  
  135.         for(i=0; i<sa.size()-1; i++)
  136.         {
  137.             if((sa[i]<n && sa[i+1]>n) || (sa[i]>n && sa[i+1]<n))
  138.             {
  139.                 if(lcp[i]==ans)
  140.                 {
  141.                     in=sa[i]<n?sa[i]:sa[i+1];
  142.  
  143.                     z.insert(s.substr(in,ans));
  144.                 }
  145.             }
  146.         }
  147.  
  148.         if(ans==0) cout<<"No common sequence."<<nl;
  149.         else
  150.         {
  151.             for(auto d:z) cout<<d<<nl;
  152.         }
  153.        
  154.         getline(cin,s);
  155.  
  156.     }
  157.     get_lost_idiot;
  158. }
  159.  
Advertisement
RAW Paste Data Copied
Advertisement