Description
对于一个给定长度为N的字符串,求它的第K小子串是什么。
Input
第一行是一个仅由小写英文字母构成的字符串S
第二行为两个整数T和K,T为0则表示不同位置的相同子串算作一个。T=1则表示不同位置的相同子串算作多个。K的意义如题所述。
Output
输出仅一行,为一个数字串,为第K小的子串。如果子串数目不足K个,则输出-1
Sample Input
aabc 0 3
Sample Output
aab
HINT
N<=5*10^5
T<2
K<=10^9
Solution
建SAM
首先对于不能重复的,那么SAM里每个节点的 \(size\) ,即出现次数,直接赋为 \(1\) 即可,然后类似与平衡树找第 \(k\) 大在SAM里面dfs就好了
对于可重复的,那么一个节点的出现次数就是parent树中的子树的和,其余跟上面一模一样
#include#define ui unsigned int#define ll long long#define db double#define ld long double#define ull unsigned long longconst int MAXN=500000+10;int n,len[MAXN<<1],fa[MAXN<<1],ch[MAXN<<1][30],cnt[MAXN],rk[MAXN<<1],las=1,tot=1,size[MAXN<<1],sum[MAXN<<1],opt,k;char s[MAXN];template inline void read(T &x){ T data=0,w=1; char ch=0; while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar(); if(ch=='-')w=-1,ch=getchar(); while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar(); x=data*w;}template inline void write(T x,char ch='\0'){ if(x<0)putchar('-'),x=-x; if(x>9)write(x/10); putchar(x%10+'0'); if(ch!='\0')putchar(ch);}template inline void chkmin(T &x,T y){x=(y inline void chkmax(T &x,T y){x=(y>x?y:x);}template inline T min(T x,T y){return x inline T max(T x,T y){return x>y?x:y;}inline void extend(int c){ int p=las,np=++tot; las=np; len[np]=len[p]+1;size[np]=1; while(p&&!ch[p][c])ch[p][c]=np,p=fa[p]; if(!p)fa[np]=1; else { int q=ch[p][c]; if(len[q]==len[p]+1)fa[np]=q; else { int nq=++tot; fa[nq]=fa[q]; memcpy(ch[nq],ch[q],sizeof(ch[nq])); len[nq]=len[p]+1,fa[q]=fa[np]=nq; while(p&&ch[p][c]==q)ch[p][c]=nq,p=fa[p]; } }}inline void dfs(int x,int k){ k-=size[x]; if(k<=0)return ; for(register int i=1;i<=26;++i) if(ch[x][i]) { if(sum[ch[x][i]]>=k) { putchar(i+'a'-1); dfs(ch[x][i],k); return ; } else k-=sum[ch[x][i]]; }}int main(){ scanf("%s",s+1); read(opt);read(k); n=strlen(s+1); for(register int i=1;i<=n;++i)extend(s[i]-'a'+1); for(register int i=1;i<=tot;++i)cnt[len[i]]++; for(register int i=1;i<=n;++i)cnt[i]+=cnt[i-1]; for(register int i=1;i<=tot;++i)rk[cnt[len[i]]--]=i; if(opt) for(register int i=tot;i>=1;--i)size[fa[rk[i]]]+=size[rk[i]]; else for(register int i=1;i<=tot;++i)size[i]=1; size[1]=0; for(register int i=tot;i>=1;--i) { sum[rk[i]]=size[rk[i]]; for(register int j=1;j<=26;++j)sum[rk[i]]+=sum[ch[rk[i]][j]]; } if(k>sum[1])puts("-1"); else dfs(1,k); return 0;}