Description

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

Input

第一行是一个仅由小写英文字母构成的字符串S

第二行为两个整数T和K，T为0则表示不同位置的相同子串算作一个。T=1则表示不同位置的相同子串算作多个。K的意义如题所述。

Output

输出仅一行，为一个数字串，为第K小的子串。如果子串数目不足K个，则输出-1

solution

和 SPOJ7258 比较类似，只不过多了一个不同位置算多次，用到 SPOJNSUBSTR 的方法，因为父亲节点是当前节点的最大子集，所以在父亲节点出现过的，在当前节点一定出现过，所以直接将 \(size\) 累加到父亲节点上即可.

注意这个时候跳的过程需要做一些改变，每跳到一个位置 \(k\) 要减去当前节点的 \(size\)，因为做了累加操作，也就是说含有这个子串的个数不止\(1\)，当\(k<=0\)时即统计完毕

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#define RG register

#define il inline

#define iter iterator

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

using namespace std;

const int N=1200005;

char s[N];int fa[N],n,ch[N][27],T,K,len[N],cnt=1,size[N],t[N],p,cur=1;

void build(int c,int id){

    p=cur;cur=++cnt;len[cur]=id;

    for(;p && !ch[p][c];p=fa[p])ch[p][c]=cur;

    if(!ch[p][c])fa[cur]=1;

    else{

        int q=ch[p][c];

        if(len[p]+1==len[q])fa[cur]=q;

        else{

            int nt=++cnt;len[nt]=len[p]+1;

            memcpy(ch[nt],ch[q],sizeof(ch[q]));

            fa[nt]=fa[q];fa[q]=fa[cur]=nt;

            for(;ch[p][c]==q;p=fa[p])ch[p][c]=nt;

        }

    }

    size[cur]=1;

}

int c[N],sa[N];

void priwork(){

    for(int i=1;i<=cnt;i++)c[len[i]]++;

    for(int i=1;i<=n;i++)c[i]+=c[i-1];

    for(int i=cnt;i>=1;i--)sa[c[len[i]]--]=i;

    for(RG int i=cnt,x;i>=1;i--){

        x=sa[i];

        if(T)size[fa[x]]+=size[x];

        else size[x]=1;

        if(x!=1)t[x]=size[x];

        for(RG int j=0;j<=25;j++)t[x]+=t[ch[x][j]];

    }

}

void solve(){

    RG int x=1,u,i;

    while(K>0){

        for(i=0;i<=25;i++){

            if(!ch[x][i])continue;

            u=ch[x][i];

            if(t[u]>=K){

                putchar(i+'a');

                x=u;K-=size[x];break;

            }

            else K-=t[u];

        }

    }

}

void work()

{

    scanf("%s%d%d",s+1,&T,&K);

    n=strlen(s+1);

    for(int i=1;i<=n;i++)build(s[i]-'a',i);

    priwork();

    if(t[1]<K){puts("-1");return ;}

    solve();

}

int main()

{

	work();

	return 0;

}