luogu P3975 [TJOI2015]弦论
链接
思路
建出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;
}