P3975 [TJOI2015] 弦论题解-526互联

一、题目描述：

　　给你一个长度为 $n$ 的字符串，字符串由 $26$ 个小写字母组成，求第 $k$ 大的字串。

　　　　给定参数 $t$ ：

　　　　$t=0:\ 位置不同的相同字串只算一个。$

　　　　$t=1:\ 位置不同的相同字串算作多个。$

　　若字串数量不足 $k$ 个，输出 $-1$ 。

　　数据范围：$1\le n\le 5\times 10^5,1\le k\le 1\times 10^9$ 。

二、解题思路：

　　后缀数组求出 $sa$ 和 $height$ 数组。

　　$t=0:$ 经典问题 $=>$ 不同字串个数，时间复杂度 $O(nlog_2^n)$ 。

　　$t=1:$ 比较复杂，细说。

　　　　考虑与 $t=0$ 时的区别，当前这这一位的字母多次出现，要算多次。

　　　　所以二分出这个字母的右边界，如果字串数量不够就跳下一个字母，否则进入下一位的判断。

　　　　由于字符串由 $26$ 个小写字母组成，所以每一轮二分次数不超过 $26$ 次，时间复杂度 $O(26\times nlog_2^n)$ 。

三、完整代码：

  1 #include<iostream>
  2 #define N 1000010
  3 using namespace std;
  4 string s;
  5 int n,m,t,k,q=122,L,R[N];
  6 int p[N];
  7 int h[N],rak[N],sa[N],tp[N];
  8 struct ST{
  9     int l,r,id;
 10     bool operator != (const ST &t) const {
 11         if(t.l!=l) return 1;
 12         if(t.r!=r) return 1;
 13         return 0;
 14     }
 15 }a[N],b[N];
 16 void qsort()
 17 {
 18     for(int i=0;i<=m;i++) tp[i]=0;
 19     for(int i=1;i<=n;i++) tp[a[i].r]++;
 20     for(int i=1;i<=m;i++) tp[i]+=tp[i-1];
 21     for(int i=n;i>=1;i--) b[tp[a[i].r]--]=a[i];
 22     for(int i=1;i<=m;i++) tp[i]=0;
 23     for(int i=1;i<=n;i++) tp[b[i].l]++;
 24     for(int i=1;i<=m;i++) tp[i]+=tp[i-1];
 25     for(int i=n;i>=1;i--) a[tp[b[i].l]--]=b[i];
 26 }
 27 void suffixsort()
 28 {
 29     for(int i=1;i<=n;i++)
 30         rak[i]=s[i-1];
 31     for(int w=1;w<=n;w<<=1)
 32     {
 33         for(int i=1;i<=n;i++)
 34             a[i].l=rak[i],a[i].r=rak[i+w],a[i].id=i;
 35         m=q;q=0;qsort();
 36         for(int i=1;i<=n;i++)
 37             rak[a[i].id]=(q+=a[i]!=a[i-1]);
 38         if(q==n) break;
 39     }
 40     for(int i=1;i<=n;i++)
 41         sa[rak[i]]=i;
 42 }
 43 void get_height()
 44 {
 45     int k=-1;
 46     for(int i=1;i<=n;i++)
 47     {
 48         if(k>=0) k--;
 49         int j=sa[rak[i]-1];
 50         while(s[i+k]==s[j+k]) k++;
 51         h[rak[i]]=k+1;
 52     }
 53 }
 54 void pre_work()
 55 {
 56     L=1;R[0]=n;
 57     for(int i=1;i<=n;i++)
 58         p[i]=p[i-1]+n-sa[i]+1;
 59 }
 60 bool check(int x,char val,int pos)
 61 {
 62     int tmp=sa[x]+pos-2;
 63     if(tmp>=n)return 0;
 64     return s[tmp]==val;
 65 }
 66 int Find(int ll,int rr,int x)
 67 {
 68     char val=s[sa[ll]+x-2];int ans;
 69     while(ll<=rr)
 70     {
 71         int mid=(ll+rr)>>1;
 72         if(check(mid,val,x)){
 73             ans=mid;
 74             ll=mid+1;
 75         }else rr=mid-1;
 76     }
 77     return ans;
 78 }
 79 int main()
 80 {
 81     ios::sync_with_stdio(false);
 82     cin.tie(0);cout.tie(0);
 83     cin>>s>>t>>k;n=s.length();
 84     suffixsort();get_height();
 85     if(t==0){
 86         for(int i=1;i<=n;i++)
 87             if(k<=n-sa[i]+1-h[i]){
 88                 for(int j=sa[i];j<sa[i]+k+h[i];j++)
 89                     cout<<s[j-1];return 0;
 90             }else k-=n-sa[i]+1-h[i];
 91         cout<<-1<<'\n';
 92     }else{
 93         pre_work();
 94         if(1ll*n*(n+1)/2<k){
 95             cout<<-1<<'\n';
 96             return 0;
 97         }
 98         for(int i=1;i<=n;i++)
 99         {
100             while(sa[L]+i-1>n&&L<n)
101                 L++;R[i]=Find(L,R[i-1],i);
102             int tmp=p[R[i]]-p[L-1]-(R[i]-L+1)*(i-1);
103             while(tmp<k)
104             {
105                 k-=tmp;L=R[i]+1;
106                 R[i]=Find(L,R[i-1],i);
107                 tmp=p[R[i]]-p[L-1]-(R[i]-L+1)*(i-1);
108             }
109             if(L==R[i]){
110                 for(int cc=1;cc<=k;cc++)
111                     cout<<s[sa[L]+i+cc-3];
112                 break;
113             }else    cout<<s[sa[L]+i-2],k-=R[i]-L+1;
114         }
115     }
116     return 0;
117 }