fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. void countSort(vector<int>&p,vector<int>&c)
  5. {
  6.     int n=p.size();
  7.     vector<int>cnt(n);
  8.     for(auto it:c) cnt[it]++;
  9.     vector<int>p_new(n),pos(n);
  10.     pos[0]=0;
  11.     for(int i=1;i<n;i++) pos[i]=pos[i-1]+cnt[i-1];
  12.     for(auto it:p)
  13.     {
  14.         int i=c[it];
  15.         p_new[pos[i]]=it;
  16.         pos[i]++;
  17.     }
  18.     p=p_new;
  19. }
  20. pair<vector<int>,vector<int>>SuffixArray_LCP(string &s)
  21. {
  22.     s+='$';
  23.     int n=s.size();
  24.     vector<pair<char,int>>suf(n);
  25.     for(int i=0;i<n;i++) suf[i]={s[i],i};
  26.     sort(suf.begin(),suf.end());
  27.     vector<int>p(n),c(n);
  28.     for(int i=0;i<n;i++) p[i]=suf[i].second;
  29.     c[p[0]]=0;
  30.     for(int i=1;i<n;i++)
  31.     {
  32.         if(suf[i].first==suf[i-1].first) c[p[i]]=c[p[i-1]];
  33.         else c[p[i]]=c[p[i-1]]+1;
  34.     }
  35.     int k=0;
  36.     while((1<<k)<n)
  37.     {
  38.         for(int i=0;i<n;i++) p[i]=(p[i]-(1<<k)+n)%n;
  39.         countSort(p,c);
  40.         vector<int>c_new(n);
  41.         c_new[p[0]]=0;
  42.         for(int i=1;i<n;i++)
  43.         {
  44.             pair<int,int>last={c[p[i-1]],c[(p[i-1]+(1<<k))%n]};
  45.             pair<int,int>cur={c[p[i]],c[(p[i]+(1<<k))%n]};
  46.             if(cur==last) c_new[p[i]]=c_new[p[i-1]];
  47.             else c_new[p[i]]=c_new[p[i-1]]+1;
  48.         }
  49.         c=c_new;
  50.         k++;
  51.     }
  52.     vector<int>lcp(n);
  53.     k=0;
  54.     for(int i=0;i<n-1;i++)
  55.     {
  56.         int pi=c[i],j=p[pi-1];
  57.         while(s[i+k]==s[j+k]) k++;
  58.         lcp[pi]=k;
  59.         k=max(k-1,0);
  60.     }
  61.     return {p,lcp};
  62. }
  63. template <typename T>
  64. struct SparseTable{
  65.     vector <T> dp[32];
  66.     T combine(const T& x, const T& y){
  67.         return min(x,y);
  68.     }
  69.     SparseTable(const vector<T> &ar){
  70.         int i, j, l, h, n = (int)ar.size();
  71.         dp[0] = ar;
  72.         for (h = 1, l = 2; l <= n; h++, l <<= 1){
  73.             dp[h].resize(n);
  74.             for (i = 0, j = i + (l / 2); (i + l) <= n; i++, j++){
  75.                 dp[h][i] = combine(dp[h - 1][i], dp[h - 1][j]);
  76.             }
  77.         }
  78.     }
  79.     T query(int l, int r){
  80.         int h = __lg(r - l + 1);
  81.         auto res = dp[h][l];
  82.         for (l += (1 << h); l <= r; l += (1 << h)){
  83.             h = __lg(r - l + 1);
  84.             res = combine(res, dp[h][l]);
  85.         }
  86.         return res;
  87.     }
  88. };
  89. signed main()
  90. {
  91.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  92.     int t;cin>>t;while(t--)
  93.     {
  94.         int n,m,q;cin>>n>>m>>q;
  95.         string a,b;cin>>a>>b;
  96.         a=a+'%'+b;
  97.         auto[suf,lcp]=SuffixArray_LCP(a);
  98.         vector<int>f(m+5);
  99.         stack<int>st;
  100.         for(int i=0;i<suf.size();i++)
  101.         {
  102.             if(suf[i]<=n)
  103.             {
  104.                 int mn=lcp[i];
  105.                 while(st.size())
  106.                 {
  107.                     f[suf[st.top()]-n-1]=mn;
  108.                     mn=min(mn,lcp[st.top()]);
  109.                     st.pop();
  110.                 }
  111.             }
  112.             else
  113.             {
  114.                 st.push(i);
  115.             }
  116.         }
  117.         stack<int>st2;
  118.         for(int i=suf.size()-1;i>=0;i--)
  119.         {
  120.             if(suf[i]>=n)
  121.             {
  122.                 st2.push(i);
  123.             }
  124.             else
  125.             {
  126.                 int mn=n+m+5;
  127.                 while(st2.size())
  128.                 {
  129.                     mn=min(mn,lcp[st2.top()]);
  130.                     f[suf[st2.top()]-n-1]=max(mn,f[suf[st2.top()]-n-1]);
  131.                     st2.pop();
  132.                 }
  133.             }
  134.         }
  135.         SparseTable<int>sp(f);
  136.         while(q--)
  137.         {
  138.             int l,r;cin>>l>>r;
  139.             --l,--r;
  140.             int L=1,R=r-l+1,ans=0;
  141.             while(L<=R)
  142.             {
  143.                 int mid=L+R>>1;
  144.                 if(sp.query(l,r-mid+1)>=mid)
  145.                 {
  146.                     ans=mid;
  147.                     L=mid+1;
  148.                 }
  149.                 else
  150.                 {
  151.                     R=mid-1;
  152.                 }
  153.             }
  154.             cout<<ans<<'\n';
  155.         }
  156.     }
  157.     return 0;
  158. }
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/b559fl
language:
C++14 (gcc 8.3)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!