LG3975 [TJOI2015]弦论

弦论

对于一个给定长度为 \(N\) 的字符串，求它的第 \(K\) 小子串。

\(T\) 为 0 则表示不同位置的相同子串算作一个。\(T\) 为 1 则表示不同位置的相同子串算作多个。

\(N \leq 5 \times 10^5, \ T<2, \ K \leq 10^9\)

分析

首先建立SAM，不同字符串对应于不同的从初始节点开始的路径，然后根据题意分类：

1. t为0则表示不同位置的相同子串算作一个，那么每个状态对应路径的字符串的出现次数只能算作1次。
2. t为1则表示不同位置的相同子串算作多个，那么每个状态对应路径的字符串的出现次数等于它的end-pos集合大小，基数排序求拓扑序后更新即可。

时间复杂度\(O(|S|)\)

代码

把初始节点设成1，即让last=tot=1会方便许多。

#include<bits/stdc++.h>

#define rg register

#define il inline

#define co const

template<class T>il T read(){

    rg T data=0,w=1;rg char ch=getchar();

    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}

    while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();

    return data*w;

}

template<class T>il T read(rg T&x) {return x=read<T>();}

typedef long long ll;

using namespace std;

co int N=5e5+5;

char s[N];

int n,t,k;

int ch[N*2][26],len[N*2],fa[N*2],siz[N*2],last=1,tot=1;

void extend(int c){

	int cur=++tot;

	len[cur]=len[last]+1,siz[cur]=1;

	int p=last;last=cur;

	for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=cur;

	if(!p) fa[cur]=1;

	else{

		int q=ch[p][c];

		if(len[q]==len[p]+1) fa[cur]=q;

		else{

			int clone=++tot;

			len[clone]=len[p]+1,copy(ch[q],ch[q]+26,ch[clone]);

			fa[clone]=fa[q],fa[q]=fa[cur]=clone;

			for(;ch[p][c]==q;p=fa[p]) ch[p][c]=clone;

		}

	}

}

int c[N],a[N*2],sum[N*2];

int main(){

	scanf("%s",s+1),n=strlen(s+1);

	read(t),read(k);

	for(int i=1;i<=n;++i) extend(s[i]-'a');

	for(int i=1;i<=tot;++i) ++c[len[i]];

	for(int i=1;i<=n;++i) c[i]+=c[i-1];

	for(int i=1;i<=tot;++i) a[c[len[i]]--]=i;

	for(int i=tot;i;--i){

		if(t) siz[fa[a[i]]]+=siz[a[i]];

		else siz[a[i]]=1;

	}

	siz[1]=0;

	for(int i=tot;i;--i){

		sum[a[i]]=siz[a[i]];

		for(int c=0;c<26;++c)

			if(ch[a[i]][c]) sum[a[i]]+=sum[ch[a[i]][c]];

	}

	if(k>sum[1]) return puts("-1"),0;

	int now=1;k-=siz[now];

	while(k){

		int c=0;

		for(;k>sum[ch[now][c]];++c) k-=sum[ch[now][c]];

		putchar('a'+c);

		now=ch[now][c],k-=siz[now];

	}

	return 0;

}