【题目链接】
http://www.lydsy.com/JudgeOnline/problem.php?id=3998
【题意】
询问排名第k的子串是谁,0代表相同子串不同位置算作相同,1代表相同子串不同位置算作不同。
【思路】
0的情况和这个题一样每个子串不同位置出现次数算作1;
至于1,统计val作为该子串在不同位置出现的次数,就是求一下|right|的大小呗,相应修改一下就可以了。
【代码】
#include<cstdio>
#include<cstring>
using namespace std; const int N = *1e5+; char s[N];
int root,last,sz,ch[N][],fa[N],sum[N],val[N],l[N];
void add(int x) {
int c=s[x]-'a';
int p=last,np=++sz; last=np;
l[np]=x+; val[np]=;
for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
if(!p) fa[np]=root;
else {
int q=ch[p][c];
if(l[p]+==l[q]) fa[np]=q;
else {
int nq=++sz; l[nq]=l[p]+;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
fa[nq]=fa[q];
fa[np]=fa[q]=nq;
for(;p&&q==ch[p][c];p=fa[p]) ch[p][c]=nq;
}
}
} int n,T,b[N],cnt[N]; void get_sum() {
for(int i=;i<=sz;i++) cnt[l[i]]++;
for(int i=;i<=n;i++) cnt[i]+=cnt[i-];
for(int i=sz;i>=;i--) b[cnt[l[i]]--]=i;
for(int i=sz;i;i--)
if(!T) val[b[i]]=;
else val[fa[b[i]]]+=val[b[i]];
val[]=;
for(int i=sz;i;i--) {
int p=b[i]; sum[p]=val[p];
for(int j=;j<;j++)
sum[p]+=sum[ch[p][j]];
}
} int main() {
scanf("%s",s);
n=strlen(s);
root=last=++sz;
for(int i=;i<n;i++) add(i);
scanf("%d",&T);
int x,p=root; scanf("%d",&x);
get_sum();
if(x>sum[]) { puts("-1");return ; }
while(x>val[p]) {
for(int c=;c<;c++)if(ch[p][c]) {
if(sum[ch[p][c]]>=x) {
putchar('a'+c);
x-=val[p]; p=ch[p][c];
break;
}
else x-=sum[ch[p][c]];
}
}
return ;
}