题目大意:

对于一个给定长度为N的字符串，求它的第K小子串是什么。

题解:

这道题我们可以类比着来做

那道题是求最小的一个字符串,而这道题是要求一个k小的字符串

所以我们瞎搞一搞就好了啊...像在平衡树上查询k小一样.

#include 
    
     #include 
     
      #include 
      
       using namespace std;typedef long long ll;inline void read(ll &x){    x=0;char ch;bool flag = false;    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;}const ll maxn = 500010;struct Node{    int nx[26];    int fa,len;}T[maxn<<1];int last,nodecnt;ll siz[maxn<<1];int num[maxn<<1];void init(){    last = nodecnt = 0;    T[0].fa = -1;T[0].len = 0;}void insert(char cha){    int c = cha - 'a',cur = ++ nodecnt,p;    T[cur].len = T[last].len+1;    for(p=last;p!=-1 && !T[p].nx[c];p=T[p].fa) T[p].nx[c] = cur;    if(p == -1) T[cur].fa = 0;    else{        int q = T[p].nx[c];        if(T[q].len == T[p].len + 1) T[cur].fa = q;        else{            int co = ++ nodecnt;            T[co] = T[q];T[co].len = T[p].len + 1;            for(;p!=-1&&T[p].nx[c] == q;p=T[p].fa) T[p].nx[c] = co;            T[cur].fa = T[q].fa = co;        }    }last = cur;    ++num[last];}inline void build(char *s){    init();int len = strlen(s);    for(int i=0;i
       
        =1;--i){        if(ty == 0) num[q[i]] = (bool)num[q[i]];        num[T[q[i]].fa] += num[q[i]];    }}void dfs(int u){    vis[u] = true;    siz[u] = num[u];    for(int c=0;c<26;++c){        if(T[u].nx[c]){            if(!vis[T[u].nx[c]]) dfs(T[u].nx[c]);            siz[u] += siz[T[u].nx[c]];        }    }return;}bool flag = false;void find(int u,ll k){    if(k <= num[u]) return;    k -= num[u];    for(int c=0;c<26;++c){        if(T[u].nx[c]){            if(k <= siz[T[u].nx[c]]){                flag = true;                putchar(c+'a');                find(T[u].nx[c],k);                return;            }k -= siz[T[u].nx[c]];        }    }return;}char s[maxn<<1];int main(){    scanf("%s",s);build(s);    ll T,K;read(T);read(K);    calc_num(T);memset(vis,0,sizeof vis);    num[0] = 0;dfs(0);    if(siz[0] < K) return puts("-1");    find(0,K);    getchar();getchar();    return 0;}