Submission #2543003

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;

const int maxn=2e4+10;
int tot=1,last=1,c[maxn],a[maxn],dp[maxn];
int k;
string s;

struct SAM{
	int link,len;
	int ch[26];
}sam[maxn];

void build(int x){
	int cur=++tot,p=last;
	sam[cur].len=sam[p].len+1;
	for(;p&&!sam[p].ch[x];p=sam[p].link)
		sam[p].ch[x]=cur;
	if(!p) sam[cur].link=1;
	else{
		int q=sam[p].ch[x];
		if(sam[q].len==sam[p].len+1) sam[cur].link=q;
		else{
			int clone=++tot;
			sam[clone]=sam[q],sam[clone].len=sam[p].len+1;
			for(;p&&sam[p].ch[x]==q;p=sam[p].link)
				sam[p].ch[x]=clone;
			sam[q].link=sam[cur].link=clone;
		}
	}last=cur;
}

void cal(){
	for(int i=1;i<=tot;i++) c[sam[i].len]++;
	for(int i=1;i<=tot;i++) c[i]+=c[i-1];
	for(int i=1;i<=tot;i++) a[c[sam[i].len]--]=i;
	for(int i=tot;i;i--){
		dp[a[i]]=1; 
		for(int j=0;j<26;j++)
			if(sam[a[i]].ch[j])
				dp[a[i]]+=dp[sam[a[i]].ch[j]];
	}
	dp[1]--;	int now=1;
	while(k){
		for(int i=0;i<26;i++){
			if(sam[now].ch[i]&&dp[sam[now].ch[i]]<k)
				k-=dp[sam[now].ch[i]];
			else if(sam[now].ch[i]){
				printf("%c",(char)i+'a');
				now=sam[now].ch[i];k--;
				goto end;
			}
		}
		return ;
		end:;
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin>>s>>k;
	for(int i=0;i<s.size();i++)
		build(s[i]-'a');
	cal();
	return 0;
}

Submission Info

Judge Result