update：把struct state里的变量s和siz改成long long，但还是全WA……
by PY_Fighter @ 2021-06-07 17:37:45
怎么没有大佬帮我qaq
by PY_Fighter @ 2021-06-07 17:38:15
@[PY_Fighter](/user/50301) 新建 clone 的时候要继承 q 的全部信息吧
by Kreap @ 2021-06-07 17:43:05
@[Kreap](/user/418438) 我写了st[clone]=st[q]，后面再改信息的
by PY_Fighter @ 2021-06-07 17:45:48
@[Kreap](/user/418438) [SAM模板](https://www.luogu.com.cn/problem/P3804)过了的
by PY_Fighter @ 2021-06-07 17:46:35
@[PY_Fighter](/user/50301) 我加了之后得了 45pts，交的你的代码
by Kreap @ 2021-06-07 17:52:00
我先吃饭
by Kreap @ 2021-06-07 17:53:09
@[Kreap](/user/418438) 我是傻逼，我之前加了的，后来因为调了太久加了一坨奇奇怪怪的东西最后重构了代码然后没加
by PY_Fighter @ 2021-06-07 17:55:14
@[Kreap](/user/418438) 然后我也忘了再测一边P3804，结果……我一直以为没写错，关键是小样例完全没问题！没用到clone！！！
by PY_Fighter @ 2021-06-07 17:56:07
update：刚发现t=0时每个节点的贡献应该都是1，t=0时把所有节点的siz都设为1现在得到了90分WA两个点，loj上测了一下发现就WA第一个点，是t=0的点，我的答案比正确答案长了一位
```cpp
#include<cstdio>
#include<algorithm>
#define N 4000005
using namespace std;
int last,cnt,num=0,ans[N];
int t,k;
bool vis[N];
struct state
{
int len,link;
long long s,siz;
int nxt[30];
};
state st[N];
struct node
{
int val,id;
};
node p[N];
void init()
{
st[0].len=0;
st[0].link=-1;
cnt=last=0;
}
void extend(int c)
{
int cur=++cnt;
st[cur].siz=1;
st[cur].len=st[last].len+1;
int p=last;
while (p!=-1&&!st[p].nxt[c])
{
st[p].nxt[c]=cur;
p=st[p].link;
}
if (p==-1) st[cur].link=0; else
{
int q=st[p].nxt[c];
if (st[q].len==st[p].len+1) st[cur].link=q; else
{
int clone=++cnt;
st[clone]=st[q];
st[clone].len=st[p].len+1;
st[clone].siz=0;
while (p!=-1&&st[p].nxt[c]==q)
{
st[p].nxt[c]=clone;
p=st[p].link;
}
st[q].link=st[cur].link=clone;
}
}
last=cur;
}
bool cmp(node x,node y)
{
return x.val>y.val;
}
void dfs(int u)
{
st[u].s=st[u].siz;
vis[u]=true;
for (int i=0;i<26;i++)
if (st[u].nxt[i])
{
if (!vis[st[u].nxt[i]]) dfs(st[u].nxt[i]);
st[u].s+=st[st[u].nxt[i]].s;
}
}
void find(int u,int k)
{
k-=st[u].siz;
if (k<=0) return;
for (int i=0;i<26;i++)
if (st[u].nxt[i])
{
if (k<=st[st[u].nxt[i]].s)
{
ans[++num]=i;
find(st[u].nxt[i],k);
break;
}
k-=st[st[u].nxt[i]].s;
}
}
int main()
{
init();
char ch=getchar();
while (ch<'a'||ch>'z') ch=getchar();
while (ch>='a'&&ch<='z')
{
extend(ch-'a');
ch=getchar();
}
scanf("%d%d",&t,&k);
if (t==1)
{
for (int i=1;i<=last;i++)
{
p[i].val=st[i].len;
p[i].id=i;
}
sort(p+1,p+last+1,cmp);
for (int i=1;i<=last;i++)
st[st[p[i].id].link].siz+=st[p[i].id].siz;
} else
{
for (int i=1;i<=last;i++)
st[i].siz=1;
}
st[0].siz=0;
dfs(0);
if (st[0].s<k)
{
printf("-1\n");
return 0;
}
find(0,k);
for (int i=1;i<=num;i++)
printf("%c",ans[i]+'a');
puts("");
return 0;
}
```
by PY_Fighter @ 2021-06-08 09:36:44