原题链接

学SAM时看到的题，oi-wiki上说SA更好做，我就写了SA，被硬控 $2$ 个小时，已经要霸占第一页提交了，来个人救救吧！

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+10;
int m,t,k,sa[N],rk[N],x[N],y[N],cnt,num,st[N][21],lg[N];
char s[N];
int n,ans=0,hi[N];
void SA()
{
	for(int i=1;i<=n;i++)rk[x[i]=s[i]]++;
	for(int i=1;i<=m;i++)rk[i]+=rk[i-1];
	for(int i=n;i>=1;i--)sa[rk[x[i]]--]=i;
	for(int k=1;k<=n;k<<=1)
	{
		cnt=0;
		for(int i=n-k+1;i<=n;i++)y[++cnt]=i;
		for(int i=1;i<=n;i++)if(sa[i]>k)y[++cnt]=sa[i]-k;
		for(int i=1;i<=m;i++)rk[i]=0;
		for(int i=1;i<=n;i++)rk[x[i]]++;
		for(int i=1;i<=m;i++)rk[i]+=rk[i-1];
		for(int i=n;i>=1;i--)sa[rk[x[y[i]]]--]=y[i],y[i]=0;
		swap(x,y);
		x[sa[1]]=1,num=1;
		for(int i=2;i<=n;i++)
		{
			x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
		}
		if(num==n)break;
		m=num;
	} 
}
void geth()
{
    int kk=0;
    for(int i=1;i<=n;i++)x[sa[i]]=i;
    for(int i=1;i<=n;i++)
    {
        if(x[i]==1)continue;
        if(kk)kk--;
        int j=sa[x[i]-1];
        while(i+kk<=n&&j+kk<=n&&s[i+kk]==s[j+kk])kk++;
        hi[x[i]]=kk;
        ans+=kk;
    }
    for(int i=1;i<=n;i++)st[i][0]=hi[i];
    for(int j=1;j<=20;j++)
    {
    	for(int i=1;i+(1<<j)-1<=n;i++)
    	st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
	}
}
void getkth(int kk,int &len,int &w)
{
	len=0;
	for(int i=1;i<=n;i++)
    {
    	int gx=n-sa[i]+1-hi[i];
    	if(gx<kk)kk-=gx;
    	else
    	{
    		len=i,w=kk;
			return ; 
		}
	}
}
int query(int xx,int yy)
{
	if(xx!=yy)xx++;
	else return n-sa[xx]+1; 
	int cd=lg[yy-xx+1];
	return min(st[xx][cd],st[yy-(1<<cd)+1][cd]);
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
    cin>>s+1;
    n=strlen(s+1);m=150;
	int len,w;
    lg[0]=-1;
	for(int i=1;i<=n;i++)lg[i]=lg[i/2]+1;
    SA();
    geth();
    cin>>t>>k;
    if(t==1)
    {
    	if(k>n*(n+1)/2)cout<<"-1"; 
    	else 
    	{
    		int l=1,r=k,jg;
    		while(l<=r)
    		{
    			int mid=(l+r)>>1,anss=0;
    			getkth(mid,len,w);
    			for(int i=1;i<len;i++)anss+=n-sa[i]+1;
    			for(int i=len;i<=n;i++)
					anss+=min(query(len,i),w);
    			if(anss>=k)jg=mid,r=mid-1;
    			else l=mid+1;
			}
			getkth(jg,len,w);
			for(int i=sa[len];i<=sa[len]+w-1;i++)cout<<s[i];	
			return 0;
		}
	}
    else
    {
    	getkth(k,len,w);
		if(len) for(int i=sa[len];i<=sa[len]+w+hi[len]-1;i++)cout<<s[i];
		else cout<<"-1";
    }
	return 0;
}