本文共 1787 字，大约阅读时间需要 5 分钟。

题目大意： 求出一个字符串第 $k$ 小的子串是谁。

题解

建出SAM，求出 $size$ 数组，即每个状态的 $endpos$ 集大小，如果 $t=0$ 的话，就将 $size$ 都设为 $1$，因为即使在多个地方出现也只算一个。要注意求完后 $size[0]$ 要等于 $0$，因为初始状态的空子串是不计入答案的。

然后求出 $sum$ 数组，$sum[x]$ 表示从状态 $x$ 出发能得到多少个子串，也就是他能到达的状态的 $size$ 之和。

然后贪心跑一下dfs即可，代码如下：

#include 
   
    #include 
    
     #define maxn 1000010int n,type,k;char s[maxn];struct state{
   	int len,link,next[26];}st[maxn];int id=0,last=0,now,p,q;int size[maxn],sum[maxn];void extend(int x){
   	now=++id;	st[now].len=st[last].len+1;size[now]=1;	for(p=last;p!=-1&&!st[p].next[x];p=st[p].link)st[p].next[x]=now;	if(p!=-1)	{
   		q=st[p].next[x];		if(st[p].len+1==st[q].len)st[now].link=q;		else		{
   			int clone=++id;			st[clone]=st[q];st[clone].len=st[p].len+1;			for(;p!=-1&&st[p].next[x]==q;p=st[p].link)st[p].next[x]=clone;			st[q].link=st[now].link=clone;		}	}	last=now;}int c[maxn],A[maxn];void get_size(){
   	if(!type){
   for(int i=1;i<=id;i++)size[i]=1;return;}	for(int i=1;i<=id;i++)c[st[i].len]++;	for(int i=1;i<=id;i++)c[i]+=c[i-1];	for(int i=1;i<=id;i++)A[c[st[i].len]--]=i;	for(int i=id;i>=1;i--)size[st[A[i]].link]+=size[A[i]];}bool v[maxn];void get_sum(int x){
   	if(v[x])return;v[x]=true;	for(int i=0;i<26;i++)	if(st[x].next[i])get_sum(st[x].next[i]),sum[x]+=sum[st[x].next[i]];}void dfs(int x){
   	k-=size[x];	if(k<=0)return;	for(int i=0;i<26;i++)	if(st[x].next[i])	{
   		if(sum[st[x].next[i]]>=k)		{
   			printf("%c",i+'a');			dfs(st[x].next[i]);			break;		}		else k-=sum[st[x].next[i]];	}}int main(){
   	scanf("%s",s+1);n=strlen(s+1);	scanf("%d %d",&type,&k);	st[0].link=-1;	for(int i=1;i<=n;i++)extend(s[i]-'a');	get_size();size[0]=0;	for(int i=0;i<=id;i++)sum[i]=size[i];	get_sum(0);	if(sum[0]
    
   

转载地址：http://ojnib.baihongyu.com/