Luogu

BZOJ

分析

首先建出后缀自动机,然后建出$\mathrm{parent}$树,求出每个节点往后能扩展出多少个串。

然后直接在 SAM 上找即可。

细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=1000010;

char s[MAXN];
int len;
int t,k;
int a[MAXN],f[MAXN];

struct Suffix_Automaton {
    int last,cnt;
    int ch[MAXN<<1][26],fa[MAXN<<1],l[MAXN<<1];
    int sz[MAXN];
    inline void ins(int c) {
        int p=last,np=++cnt; last=np,l[np]=l[p]+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 (l[p]+1==l[q]) fa[np]=q;
            else {
                int nq=++cnt; l[nq]=l[p]+1;
                memcpy(ch[nq],ch[q],sizeof(ch[q]));
                fa[nq]=fa[q],fa[q]=fa[np]=nq;
                for (;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
            }
        }
        sz[np]=1;
    }
    inline void build() {
        last=cnt=1;
        for (re int i=1;i<=len;++i) ins(s[i]-'a');
    }
    int a[MAXN],c[MAXN],f[MAXN];
    inline void query(int u,int k) {
        if (k<=sz[u]) return;
        k-=sz[u];
        for (re int i=0;i<26;++i) {
            if (!ch[u][i]) continue;
            if (f[ch[u][i]]<k) k-=f[ch[u][i]];
            else {
                putchar(i+'a');
                query(ch[u][i],k);
                return;
            }
        }
    }
    inline void solve() {
        for (re int i=1;i<=cnt;++i) ++c[l[i]];
        for (re int i=1;i<=cnt;++i) c[i]+=c[i-1];
        for (re int i=1;i<=cnt;++i) a[c[l[i]]--]=i;
        for (re int i=cnt;i;--i) sz[fa[a[i]]]+=sz[a[i]];
        for (re int i=1;i<=cnt;++i) {
            if (!t) f[i]=sz[i]=1;
            else f[i]=sz[i];
        }
        f[1]=sz[1]=0;
        for (re int i=cnt;i;--i)
            for (re int j=0;j<26;++j)
                if (ch[a[i]][j]) f[a[i]]+=f[ch[a[i]][j]];
        if (k>f[1]) puts("-1"); //没有k个子串
        else query(1,k),putchar('\n');
    }
} SAM;

int main() {
    scanf("%s",s+1); len=strlen(s+1);
    t=read(),k=read();
    SAM.build();
    SAM.solve();
    return 0;
}
最后修改:2019 年 09 月 24 日 08 : 14 PM