3998: [TJOI2015]弦论
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 2152 Solved: 716
[Submit][Status][Discuss]
Description
对于一个给定长度为N的字符串，求它的第K小子串是什么。
Input
第一行是一个仅由小写英文字母构成的字符串S
第二行为两个整数T和K，T为0则表示不同位置的相同子串算作一个。T=1则表示不同位置的相同子串算作多个。K的意义如题所述。
Output
输出仅一行，为一个数字串，为第K小的子串。如果子串数目不足K个，则输出-1
T=1和上一题一样
T=2的话，每个状态不是代表一个子串，而是代表|Right|个子串，然后一样了
判断无解也可以直接与sum[root]比较哦
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int N=1e6+;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return x*f;
} int n,Type,k;
int c[N],a[N],d[N],sum[N];
char s[N];
struct State{
int ch[],par,val;
}t[N];
int sz,root,last;
inline int nw(int _){t[++sz].val=_;return sz;}
inline void iniSAM(){sz=;root=last=nw();}
void extend(int c){
int p=last,np=nw(t[p].val+);d[np]=;
for(;p&&!t[p].ch[c];p=t[p].par) t[p].ch[c]=np;
if(!p) t[np].par=root;
else{
int q=t[p].ch[c];
if(t[q].val==t[p].val+) t[np].par=q;
else{
int nq=nw(t[p].val+);
memcpy(t[nq].ch,t[q].ch,sizeof(t[q].ch));
t[nq].par=t[q].par;
t[q].par=t[np].par=nq;
for(;p&&t[p].ch[c]==q;p=t[p].par) t[p].ch[c]=nq;
}
}
last=np;
}
void RadixSort(){
for(int i=;i<=sz;i++) c[t[i].val]++;
for(int i=;i<=n;i++) c[i]+=c[i-];
for(int i=;i<=sz;i++) a[c[t[i].val]--]=i;
}
void dp(){
RadixSort();
for(int i=sz;i>=;i--){
int u=a[i];
if(Type==) d[t[u].par]+=d[u];
else d[u]=;
}
for(int i=sz;i>=;i--){
int u=a[i];
sum[u]=d[u];
for(int j=;j<;j++) sum[u]+=sum[t[u].ch[j]];
}
}
int ans[N],p;
void kth(int k){
int u=root;
while(k>){
for(int i=;i<;i++) if(t[u].ch[i]){
int v=t[u].ch[i];
if(sum[v]>=k) {ans[++p]=i;k-=d[v];u=v;break;}
else k-=sum[v];
}
}
}
int main(){
freopen("in","r",stdin);
scanf("%s",s+);
n=strlen(s+);
iniSAM();
for(int i=;i<=n;i++) extend(s[i]-'a');
Type=read();k=read();
dp();
if(sum[]<k) puts("-1");
else{
kth(k);
for(int i=;i<=p;i++) putchar(ans[i]+'a');
}
}