Advertisement
Saleh127

Light OJ 1314 / Suffix Array-LCP

Aug 10th, 2022
622
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.11 KB | None | 0 0
  1. /***
  2.  created: 2022-08-10-19.53.51
  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. vector<int> sac(string s)
  17. {
  18.     s += '`';
  19.     int n = s.size();
  20.     const int A=28;
  21.     vector<int> p(n), c(n), cnt(max(n, A));
  22.     for (int i = 0; i < n; ++i) cnt[s[i]-'`']++;
  23.     for (int i = 1; i < A; ++i) cnt[i] += cnt[i-1];
  24.     for (int i = n-1; i >=0; --i) p[--cnt[s[i]-'`']] = i;
  25.     int rnk = 1;
  26.     for (int i = 1; i < n; ++i)
  27.     {
  28.         if(s[p[i]] != s[p[i-1]])  rnk++;
  29.         c[p[i]] = rnk-1;
  30.     }
  31.  
  32.     vector<int> pn(n), cn(n);
  33.     for (int k = 0; (1<<k) < n; ++k)
  34.     {
  35.         for (int i = 0; i < n; ++i)
  36.         {
  37.             pn[i] = p[i] - (1<<k);
  38.             if(pn[i] < 0) pn[i] += n;
  39.         }
  40.         fill(cnt.begin(), cnt.begin()+rnk, 0);
  41.         for (int i = 0; i < n; ++i) cnt[c[pn[i]]]++;
  42.         for (int i = 1; i < rnk; ++i) cnt[i] += cnt[i-1];
  43.         for (int i = n-1; i >= 0; --i) p[--cnt[c[pn[i]]]] = pn[i];
  44.  
  45.         cn[p[0]]=0;
  46.         rnk = 1;
  47.         for (int i = 1; i < n; ++i)
  48.         {
  49.             int x = p[i]+(1<<k), y = p[i-1]+(1<<k);
  50.             if(x >= n)  x -= n;
  51.             if(y >= n)  y -= n;
  52.             pair<int, int> cur = {c[p[i]], c[x]};
  53.             pair<int, int> prev = {c[p[i-1]], c[y]};
  54.             if(cur != prev) rnk++;
  55.             cn[p[i]] = rnk-1;
  56.         }
  57.         c.swap(cn);
  58.     }
  59.  
  60.     p.erase(p.begin());
  61.     return p;
  62. }
  63.  
  64. //kasai's alog :: O(n)
  65.  
  66. vector<int> LCP(string s, vector<int> p)
  67. {
  68.     int n = s.size();
  69.     vector<int> idx(n);
  70.     for (int i = 0; i < n; ++i) idx[p[i]] = i;
  71.     int k = 0;
  72.     vector<int> lcp(n-1);
  73.     for (int i = 0; i < n; ++i)
  74.     {
  75.         if(idx[i]==n-1)
  76.         {
  77.             k = 0;
  78.             continue;
  79.         }
  80.         int j = p[idx[i]+1];
  81.         while(i+k<n and j+k<n and s[i+k]==s[j+k]) k++;
  82.         lcp[idx[i]] = k;
  83.         if(k) k--;
  84.     }
  85.     return lcp;
  86. }
  87.  
  88.  
  89. int N_Different_Substrings(const vector<int> &lcp,string b)
  90. {
  91.     int n=b.size();
  92.  
  93.     int 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;
  114.  
  115.         int n,m,i,p,q,l,r,ans=0;
  116.  
  117.         cin>>a;
  118.         cin>>p>>q;
  119.  
  120.         n=a.size();
  121.  
  122.         vector<int>sa =sac(a);
  123.  
  124.         vector<int>lcp =LCP(a,sa);
  125.  
  126.         l=1;
  127.         r=n-sa[0];
  128.  
  129.         l=max(l,p);
  130.         r=min(r,q);
  131.  
  132.         if(l<=r) ans+=(r-l+1);
  133.  
  134.         for(i=0; i<n-1; i++)
  135.         {
  136.             l=lcp[i]+1;
  137.             r=n-sa[i+1];
  138.  
  139.             l=max(l,p);
  140.             r=min(r,q);
  141.  
  142.             if(l<=r) ans+=(r-l+1);
  143.         }
  144.  
  145.         cout<<"Case "<<cs<<": "<<ans<<nl;
  146.  
  147.     }
  148.  
  149.  
  150.     get_lost_idiot;
  151. }
  152.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement