[bzoj3998][TJOI2015]弦论_后缀自动机
弦论 bzoj-3998 TJOI-2015
题目大意：给定一个字符串，求其$k$小子串。
注释：$1\le length \le 5\cdot 10^5$，$1\le k\le 10^9$。
想法：
后缀数组***题。
初学后缀自动机我们尝试用后缀自动机解决。
首先先建出$SAM$。
分别考虑$T=0$和$T=1$的情况。
我们处理$f$数组表示以当前节点代表的字符串为前缀的子串个数。
它们俩之间的区别就是$Right$集合的大小。
详情看代码把。
代码：
#include <bits/stdc++.h>
#define N 1000010
using namespace std;
int n,opt,nxt[N][26],fa[N],dis[N],lst=1,cnt=1,v[N],q[N],Right[N],f[N];
char str[N];
void update(int c)
{
int p=lst,np=lst=++cnt;
dis[np]=dis[p]+1; Right[np]=1;
while(p&&!nxt[p][c]) nxt[p][c]=np,p=fa[p];
if(!p) fa[np]=1;
else
{
int q=nxt[p][c];
if(dis[q]==dis[p]+1) fa[np]=q;
else
{
int nq=++cnt;
memcpy(nxt[nq],nxt[q],sizeof nxt[q]);
dis[nq]=dis[p]+1; fa[nq]=fa[q]; fa[np]=fa[q]=nq;
while(p&&nxt[p][c]==q) nxt[p][c]=nq,p=fa[p];
}
}
}
void init()
{
for(int i=1;i<=cnt;i++) v[dis[i]]++;
for(int i=1;i<=n;i++) v[i]+=v[i-1];
for(int i=cnt;i;i--) q[v[dis[i]]--]=i;
for(int i=cnt;i;i--)
{
int t=q[i];
if(opt) Right[fa[t]]+=Right[t];
else Right[t]=1;
}
Right[1]=0; for(int i=cnt;i;i--)
{
int t=q[i]; f[t]=Right[t];
for(int j=0;j<26;j++) f[t]+=f[nxt[t][j]];
}
}
void query(int p,int k)
{
if(k<=Right[p]) return;
k-=Right[p];
for(int i=0;i<26;i++) if(nxt[p][i])
{
if(k<=f[nxt[p][i]])
{
putchar(i+'a'); query(nxt[p][i],k);
return;
}
k-=f[nxt[p][i]];
}
}
int main()
{
int k; scanf("%s%d%d",str+1,&opt,&k); n=strlen(str+1);
for(int i=1;i<=n;i++) update(str[i]-'a');
init();
if(k>f[1]) puts("-1");
else query(1,k);
return 0;
}
小结：后缀自动机搭配其他的数据结构的时候会比较有用，但是感觉后缀数组更好写啊$qwq$......
