luogu P3975 [TJOI2015]弦论

链接

bzoj

思路

建出sam。
子串算多个的，统计preant tree的子树大小，否则就是大小为1
然后再统计sam的节点能走到多少串。
然后就可以在sam的贪心的走了。

代码

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define ROF(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
const int N=5e5+7;
int n,t,k,c[N<<1],a[N<<1];
char s[N];
struct node {
    int len,fa,ch[26];
}dian[N<<1];
int siz[N<<1],las=1,tot=1,sum[N<<1];
void add(int c) {
    int p=las;int np=las=++tot;
    dian[np].len=dian[p].len+1;
    for(;p&&!dian[p].ch[c];p=dian[p].fa) dian[p].ch[c]=np;
    if(!p) dian[np].fa=1;
    else {
        int q=dian[p].ch[c];
        if(dian[q].len==dian[p].len+1) dian[np].fa=q;
        else {
            int nq=++tot;
            dian[nq]=dian[q];
            dian[nq].len=dian[p].len+1;
            dian[q].fa=dian[np].fa=nq;
            for(;p&&dian[p].ch[c]==q;p=dian[p].fa)
                dian[p].ch[c]=nq;
        }
    }
    siz[las]=1;
}
int js;
void find(int u,int k) {
    if(k<=siz[u]) return;
    k-=siz[u];
    FOR(i,0,25) {
        if(sum[dian[u].ch[i]]>=k) {
            printf("%c",'a'+i);
            find(dian[u].ch[i],k);
            return;
        }
        k-=sum[dian[u].ch[i]];
    }
}
int main() {
    scanf("%s",s+1);
    n=strlen(s+1);
    scanf("%d%d",&t,&k);
    FOR(i,1,n) add(s[i]-'a');
    FOR(i,1,tot) c[dian[i].len]++;
    FOR(i,1,tot) c[i]+=c[i-1];
    FOR(i,1,tot) a[c[dian[i].len]--]=i;
    ROF(i,tot,1) 
        if(t) siz[dian[a[i]].fa]+=siz[a[i]];
        else siz[a[i]]=1;
    siz[0]=siz[1]=0;
    ROF(i,tot,1) {
        sum[a[i]]+=siz[a[i]];
        FOR(j,0,25) sum[a[i]]+=sum[dian[a[i]].ch[j]];
    }
    if(k>sum[1]) puts("-1");
    else find(1,k);
    return 0;
}