C++14(g++5.4) 解法, 执行用时: 194ms, 内存消耗: 84160K, 提交时间: 2020-07-31 14:52:10

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+100;
typedef long long ll;

char s[N];
int ch[N*2][26],len[N*2],fa[N*2];
int last=1,tot=1;
int endpos_size[N],c[N];//
void add(int c) {
    int p=last,np=last=++tot;
    len[np]=len[p]+1; endpos_size[np]=1;
    for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
    if(!p) fa[np]=1;
    else {
        int q=ch[p][c];
        if(len[q]==len[p]+1) fa[np]=q;
        else {
            int nq=++tot;len[nq]=len[p]+1;
            memcpy(ch[nq],ch[q],sizeof(ch[q]));
            fa[nq]=fa[q];fa[q]=fa[np]=nq;
            for(;p&&ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
        }
    }
}

int a[N],t,k,siz[N];

void getans(int x,int k) {
    if(endpos_size[x]>=k) return ;
    k-=endpos_size[x];
    for(int i=0;i<26;i++) if(ch[x][i]) {
        int v=ch[x][i];
        if(siz[v]>=k) {
            printf("%c",i+'a');
            return (void)(getans(v,k));
        }
        k-=siz[v];
    }
}

int main() {
    cin>>s+1>>t>>k;
    for(int i=1;s[i];i++) add(s[i]-'a');
    for(int i=1;i<=tot;i++) c[len[i]]++;
    for(int i=1;i<=tot;i++) c[i]+=c[i-1];
    for(int i=1;i<=tot;i++) a[c[len[i]]--]=i;
    for(int i=tot;i;i--) {
        int p=a[i];
        if(t) endpos_size[fa[p]]+=endpos_size[p];
        else endpos_size[fa[p]]=1;
    }
    endpos_size[1]=0;
    for(int i=tot;i;i--) {
        int p=a[i];
        siz[p]=endpos_size[p];
        for(int j=0;j<26;j++) if(ch[p][j])
            siz[p]+=siz[ch[p][j]];
    }
    if(siz[1]<k) puts("-1");
    else getans(1,k);
}

C++11(clang++ 3.9) 解法, 执行用时: 141ms, 内存消耗: 86692K, 提交时间: 2020-10-08 17:01:58

#include<iostream>
#include<cstring>
#include<string>
using namespace std;
const int maxn=1e6+9;
int len[maxn<<1],link[maxn<<1],nxt[maxn<<1][27],sum[maxn<<1],q[maxn<<1],v[maxn<<1],val[maxn<<1];
string s;
int T,K,idx=1,last=1;
void extend(int c){
	int x=++idx;
	len[x]=len[last]+1;
	int p;val[x]=1;
	for(p=last;p&&!nxt[p][c];p=link[p])	nxt[p][c]=x;
	if(!p)	link[x]=1;
	else{
		int q=nxt[p][c];
		if(len[q]==len[p]+1)	link[x]=q;
		else{
			int nq=++idx;
			len[nq]=len[p]+1;
			link[nq]=link[q];
			memcpy(nxt[nq], nxt[q], sizeof(nxt[q]));  //复制q的信息给nq
			for(;nq&&nxt[p][c]==q;p=link[p])	nxt[p][c]=nq;
			link[x]=link[q]=nq;
		}
	}
	last=x;
}
void pre(){
	for(int i=1;i<=idx;i++)v[len[i]]++;
	for(int i=1;i<=s.size();i++)v[i]+=v[i-1];
	for(int i=idx;i;i--)q[v[len[i]]--]=i;
	for(int i=idx;i;i--)
	{
		int t=q[i];
		if(T==1)	val[link[t]]+=val[t];
		else val[t]=1;
	}
	val[1]=0;
	for(int i=idx;i;i--)
	{
		int t=q[i];sum[t]=val[t];
		for(int j=0;j<26;j++)
			sum[t]+=sum[nxt[t][j]];
	}
}
void dfs(int x,int K){
	if(K<=val[x])return;
	K-=val[x];
	for(int i=0;i<26;i++)
		if(int t=nxt[x][i])
		{
			if(K<=sum[t])
			{
				putchar(i+'a');
				dfs(t,K);
				return;
			}
			K-=sum[t];
		}
}
int main(){
	cin>>s;
	cin>>T>>K;
	for(int i=0;i<s.size();i++)	extend(s[i]-'a');
	pre();
	if(K>sum[1])	cout<<"-1\n";
	else	dfs(1,K);
}