题解 SP7258 【SUBLEX - Lexicographical Substring Search】
devout
2020-12-22 19:55:53
**description**
给定一个字符串，求本质不同的第 $k$ 小的子串
**solution**
我们先对于这个字符串建立 SAM。
那么考虑SAM上的每个点，起点到他的路径上对应的就是一个唯一的子串。所以对于每一个点，我们可以求出以这个点对应的状态为前缀的子串的个数有多少。
求法就是对于 maxlen 从大到小排序，然后对于每个点 $u$,$siz[u]=1+\sum siz[v]$
然后我们考虑类似于平衡树求第 $k$ 大的做法，我们从小到大枚举当前点的出边，如果 $k>siz[v]$，那么 $k=k-siz[v]$，考虑下一个出边，直到第一个 $k<siz[v]$，就往这里走。
复杂度 $\mathcal O(nq)$
注意开始的时候我们不能用dfs/bfs去处理这个东西，因为SAM的自动机上的边其实是一个图，所以会出现问题。
**code**
```cpp
# include <bits/stdc++.h>
using namespace std;
# define Rep(i,a,b) for(register int i=a;i<=b;i++)
# define _Rep(i,a,b) for(register int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)
typedef long long ll;
const int N=1e5+5;
template<typename T> void read(T &x){
x=0;int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
x*=f;
}
int n,q;
char s[N];
int link[N<<1],sam[N<<1][26],maxlen[N<<1];
int siz[N<<1];
int lst=1,tot=1;
struct misaka{
int len,id;
bool operator < (const misaka &cmp)const{
return len<cmp.len;
}
}a[N<<1];
void insert(int x){
int now=++tot,p;
maxlen[now]=maxlen[lst]+1;
for(p=lst;p&&!sam[p][x];p=link[p])sam[p][x]=now;
if(!p)link[now]=1;
else{
int q=sam[p][x];
if(maxlen[q]==maxlen[p]+1)link[now]=q;
else{
int clone=++tot;
link[clone]=link[q];
maxlen[clone]=maxlen[p]+1;
memcpy(sam[clone],sam[q],sizeof(sam[q]));
for(;p&&sam[p][x]==q;p=link[p])sam[p][x]=clone;
link[q]=link[now]=clone;
}
}
lst=now;
}
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
Rep(i,1,n)insert(s[i]-'a');
Rep(i,1,tot)a[i]=(misaka){maxlen[i],i};
sort(a+1,a+tot+1);
_Rep(i,tot,1){
int u=a[i].id;
siz[u]=1;
Rep(i,0,25){
int v=sam[u][i];
if(!v)continue;
siz[u]+=siz[v];
}
}
read(q);
while(q--){
int k;
read(k);
int u=1;
k++;
while(k>1){
k--;
Rep(i,0,25){
int v=sam[u][i];
if(!v)continue;
if(k<=siz[v]){
printf("%c",i+'a');
u=v;
break;
}
else k-=siz[v];
}
}
puts("");
}
return 0;
}
```