一、题目描述：
给你一个长度为 $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 }
四、写题心得：
个人觉得是比较版也比较难的 $sa$ 题。细节比较多，但是一遍就过了！收获经验如下：
$1、sa\ 写的很熟练，值得表扬!=> Exp++!$
$2、记得乘法的时候检查要不要开\ long\ long\ 。=> Exp++!$
标签：26,return,P3975,int,题解,弦论,--,字串,sa From： https://www.cnblogs.com/yhy-trh/p/P3975.html