SAM题解

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int ch[1000010][27],len[1000100],fa[1000010],id=1,np=1;
ll sz[1000010],vis[1000100];
void extend(int c){
	int p=np;np=++id;
	sz[np]=1;
	len[np]=len[p]+1;
	for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np;
	if(!p)fa[np]=1;
	else{
		int q=ch[p][c];
		if(len[q]==len[p]+1)fa[np]=q;
		else{
			int nq=++id;
			len[nq]=len[p]+1;
			fa[nq]=fa[q];fa[q]=nq;fa[np]=nq;
			for(;p&&ch[p][c]==q;p=fa[p])ch[p][c]=nq;
			memcpy(ch[nq],ch[q],sizeof(ch[q]));
		}
	}
}
vector<int> e[1000010];
int vs[1000010];
void dfs(int x){
	for(int y:e[x]){
		dfs(y);
		sz[x]+=sz[y];
	}
}
void dfs2(int x){
	vs[x]=1;
	for(int i=0;i<26;i++)if(ch[x][i]){
		if(!vs[ch[x][i]])dfs2(ch[x][i]);
		sz[x]+=sz[ch[x][i]];
	}
}
void dfs3(int x,int k){
	if(k<=vis[x])return ;
	k-=vis[x];
	for(int i=0;i<26;i++)if(ch[x][i]){
		if(sz[ch[x][i]]>=k){
			cout<<(char)('a'+i);
			dfs3(ch[x][i],k);
			break;
		}
		else{
			k-=sz[ch[x][i]];
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s;
	cin>>s;
	for(char i:s)extend(i-'a');
	int T,k;
	cin>>T>>k;
	if(T==0){
		for(int i=2;i<=id;i++)sz[i]=1;
	}
	else{
		for(int i=2;i<=id;i++)e[fa[i]].push_back(i);
		dfs(1);
		sz[1]=0;
	}
	for(int i=1;i<=id;i++)vis[i]=sz[i];
	dfs2(1);
	if(sz[1]<k)cout<<-1;
	else dfs3(1,k);
	return 0;
}

蒟蒻的blog

Solution

• 本题解中字符串的先后均按后缀排序顺序的先后。
• 由于 $t\in\{0,1\}$，考虑从 $t$ 入手。
• 当 $t=0$ 时，显然是经典的后缀数组问题，可以直接求解。
• 当 $t=1$ 时，我们按照 $t=0$ 的方法求，会有一个思路：只要求出满足 $\sum_{i=1}^{pos-1}{n+1-sa[i]}\le k$ 的最后一个 $pos$ 就是答案。
• 但实际上这个算法有一些问题，我们按照上面求出的第 $k$ 小的字符串实际上会比实际答案大，因为在这个串后仍存在与这个串的公共前缀前缀可以计入答案，实际上这个串的排名是

$$rank=\sum_{i=1}^{pos-1}{n+1-sa[i]}+len+\sum_{i=pos+1}^{n}{\min(len,\min_{j=pos+1}^{i}{\{height[j]}\})}$$

而且我们会发现一个单调性：对于不重复子串排名的单调递增，在重复子串中的排名也必然是单调递增的。

• 考虑二分。 每次二分所有不重复的子串中排名为 $mid$ 的字符串，判断是否 $rank\le k$，其中由于从 $pos+1$ 枚举到 $n$，可以直接在向后遍历的过程中维护 $height$ 的最小值。 单次检验时间复杂度 $O(n)$，总体时间复杂度为 $O(n\log n+n\log k)$

Code

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn=500010,INF=0x3fffffff;
template<class T>inline T Min(const T &a,const T &b){return a<b?a:b;}
char s[maxn];
int sa[maxn],x[maxn],y[maxn],c[maxn],n,m;
int rk[maxn],height[maxn],t,k;
inline void get_sa(){
	for(int i=1;i<=n;++i)++c[x[i]=s[i]];
	for(int i=2;i<=m;++i)c[i]+=c[i-1];
	for(int i=n;i;--i)sa[c[x[i]]--]=i;
	for(int k=1;k<=n;k<<=1){
		int num=0;
		for(int i=n-k+1;i<=n;++i)y[++num]=i;
		for(int i=1;i<=n;++i)
			if(sa[i]>k)y[++num]=sa[i]-k;
		for(int i=1;i<=m;++i)c[i]=0;
		for(int i=1;i<=n;++i)++c[x[i]];
		for(int i=2;i<=m;++i)c[i]+=c[i-1];
		for(int i=n;i;--i)sa[c[x[y[i]]]--]=y[i],y[i]=0;
		swap(x,y);
		x[sa[1]]=1;num=1;
		for(int i=2;i<=n;++i)
			x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
		if(num==n)break;
		m=num;
	}
}
inline void get_height(){
	for(int i=1;i<=n;++i)rk[sa[i]]=i;
	for(int i=1,k=0;i<=n;++i){
		if(rk[i]==1)continue;
		if(k)--k;
		int j=sa[rk[i]-1];
		while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])++k;
		height[rk[i]]=k;
	}
}
inline void find_kth(LL k,int &pos,int &len){
	LL cnt=0;
	for(int i=1;i<=n;++i){
		if(cnt+n+1-sa[i]-height[i]>=k){
			pos=i;
			len=k-cnt+height[i];
			return;
		}
		else cnt+=n+1-sa[i]-height[i];
	}
}
inline bool check(LL mid){
	int pos,len,minh=INF;
	LL cnt=0;
	find_kth(mid,pos,len);
	for(int i=1;i<pos;++i)
		cnt+=n+1-sa[i];
	for(int i=pos+1;i<=n;++i){
		minh=Min(minh,height[i]);
		cnt+=Min(len,minh);
	}
	if(len+cnt<=k)return true;
	else return false;
}
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);m='z';
	scanf("%d%d",&t,&k);
	get_sa();get_height();
	if(t==0){
		LL sum=0;
		for(int i=1;i<=n;++i)
			sum+=n+1-sa[i]-height[i];
		if(sum<k){
			puts("-1");
			return 0;
		}
		int pos,len;
		find_kth(k,pos,len);
		for(int i=0;i<len;++i)
			putchar(s[sa[pos]+i]);
	}
	else{
		if(1ll*n*(n+1)/2<k){
			puts("-1");
			return 0;
		}
		LL l=1,r=k;
		while(l<r){
			int mid=(l+r+1)>>1;
			if(check(mid))l=mid;
			else r=mid-1;
		}
		int pos,len;
		find_kth(l,pos,len);
		for(int i=0;i<len;++i)
			putchar(s[sa[pos]+i]);
	}
	return 0;
}