Advertisement
Saleh127

UVA 12613 / Suffix Array

Jul 7th, 2022
693
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.57 KB | None
  1. /***
  2.  created: 2022-07-07-16.36.57
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. #include <ext/pb_ds/assoc_container.hpp>
  7. #include <ext/pb_ds/tree_policy.hpp>
  8. using namespace std;
  9. using namespace __gnu_pbds;
  10. template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
  11. #define ll long long
  12. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  13. #define get_lost_idiot return 0
  14. #define nl '\n'
  15.  
  16.  
  17. vector<int> sac(string s)
  18. {
  19.     s += '`';
  20.     int n = s.size();
  21.     const int A=28;
  22.     vector<int> p(n), c(n), cnt(max(n, A));
  23.     for (int i = 0; i < n; ++i) cnt[s[i]-'`']++;
  24.     for (int i = 1; i < A; ++i) cnt[i] += cnt[i-1];
  25.     for (int i = n-1; i >=0; --i) p[--cnt[s[i]-'`']] = i;
  26.     int rnk = 1;
  27.     for (int i = 1; i < n; ++i)
  28.     {
  29.         if(s[p[i]] != s[p[i-1]])  rnk++;
  30.         c[p[i]] = rnk-1;
  31.     }
  32.  
  33.     vector<int> pn(n), cn(n);
  34.     for (int k = 0; (1<<k) < n; ++k)
  35.     {
  36.         for (int i = 0; i < n; ++i)
  37.         {
  38.             pn[i] = p[i] - (1<<k);
  39.             if(pn[i] < 0) pn[i] += n;
  40.         }
  41.         fill(cnt.begin(), cnt.begin()+rnk, 0);
  42.         for (int i = 0; i < n; ++i) cnt[c[pn[i]]]++;
  43.         for (int i = 1; i < rnk; ++i) cnt[i] += cnt[i-1];
  44.         for (int i = n-1; i >= 0; --i) p[--cnt[c[pn[i]]]] = pn[i];
  45.  
  46.         cn[p[0]]=0;
  47.         rnk = 1;
  48.         for (int i = 1; i < n; ++i)
  49.         {
  50.             int x = p[i]+(1<<k), y = p[i-1]+(1<<k);
  51.             if(x >= n)  x -= n;
  52.             if(y >= n)  y -= n;
  53.             pair<int, int> cur = {c[p[i]], c[x]};
  54.             pair<int, int> prev = {c[p[i-1]], c[y]};
  55.             if(cur != prev) rnk++;
  56.             cn[p[i]] = rnk-1;
  57.         }
  58.         c.swap(cn);
  59.     }
  60.  
  61.     p.erase(p.begin());
  62.     return p;
  63. }
  64.  
  65. //kasai's alog :: O(n)
  66.  
  67. vector<int> LCP(string s, vector<int> p)
  68. {
  69.     int n = s.size();
  70.     vector<int> idx(n);
  71.     for (int i = 0; i < n; ++i) idx[p[i]] = i;
  72.     int k = 0;
  73.     vector<int> lcp(n-1);
  74.     for (int i = 0; i < n; ++i)
  75.     {
  76.         if(idx[i]==n-1)
  77.         {
  78.             k = 0;
  79.             continue;
  80.         }
  81.         int j = p[idx[i]+1];
  82.         while(i+k<n and j+k<n and s[i+k]==s[j+k]) k++;
  83.         lcp[idx[i]] = k;
  84.         if(k) k--;
  85.     }
  86.     return lcp;
  87. }
  88.  
  89. ll N_Different_Substrings(const vector<int> &lcp,string b)
  90. {
  91.     ll n=b.size();
  92.  
  93.     ll res = n*(n+1)/2;
  94.  
  95.     for(int i=0;i<lcp.size();i++)
  96.     {
  97.         res-=lcp[i];
  98.     }
  99.  
  100.     return res;
  101. }
  102.  
  103.  
  104.  
  105. int main()
  106. {
  107.     ios_base::sync_with_stdio(0);
  108.     cin.tie(0);
  109.     cout.tie(0);
  110.  
  111.     test
  112.     {
  113.         string a,b;
  114.  
  115.         ll n,m,i,j,k,l,s2,s3;
  116.  
  117.         cin>>a>>k;
  118.  
  119.         cout<<"Case "<<cs<<": ";
  120.  
  121.  
  122.         set<ll>x;
  123.  
  124.         for(i=0;a[i];i++)
  125.         {
  126.             x.insert(a[i]);
  127.         }
  128.  
  129.  
  130.         if(a.size()==x.size())
  131.         {
  132.             n=a.size();
  133.  
  134.             l=n*((n*k)-n) + (n*(n+1))/2;
  135.  
  136.             cout<<l<<nl;
  137.  
  138.             continue;
  139.         }
  140.  
  141.  
  142.         b=a;
  143.  
  144.         b+=a;
  145.  
  146.         vector<int>sa =sac(b);
  147.  
  148.         vector<int>lcp =LCP(b,sa);
  149.  
  150.         s2=N_Different_Substrings(lcp,b);
  151.  
  152.  
  153.         if(k-2==0)
  154.         {
  155.  
  156. //            for(auto i:sa) cout<<i<<" ";
  157. //            cout<<nl;
  158. //            for(auto i:lcp) cout<<i<<" ";
  159. //            cout<<nl;
  160.  
  161.             cout<<s2<<nl;
  162.             continue;
  163.         }
  164.  
  165.  
  166.         b=a;
  167.  
  168.         b+=a;
  169.         b+=a;
  170.  
  171.  
  172.         sa.clear();
  173.         lcp.clear();
  174.  
  175.         sa =sac(b);
  176.  
  177.         lcp =LCP(b,sa);
  178.  
  179.         s3=N_Different_Substrings(lcp,b);
  180.  
  181.         cout<<(s3-s2)*(k-2) + s2<<nl;
  182.  
  183.     }
  184.  
  185.  
  186.     get_lost_idiot;
  187. }
  188.  
Advertisement
RAW Paste Data Copied
Advertisement