P3975 [TJOI2015]弦論
一定要記得初始化!
字尾連結連接配接的節點所表示的字元串是該節點表示字元串的字尾,先将所有新增節點的
dp[i]
都置為1(除了拆點),一個節點所表示字元串的出現次數是其子樹所有
dp
值之和(下标不同,本質相同的兩個串是不同串)
如果下标不同,本質相同的兩個串屬于一個串的話,那麼所有的
dp[i]
為1即可。因為,字尾樹的所有節點包括了所有的子串。然後再按照
Next
轉移即可。
Next 表示的是轉移,通過每個節點的轉移,可以得到字尾樹中的所有子串
link 指向的是子串,是以 p 指向的節點一定會讓 link[p] 表示的字元串在除 link[p] 表示的位置再出現一次。
// Created by CAD
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
namespace sam{
int len[maxn],link[maxn],Next[maxn][26];
int sz,last;
int dp[maxn];
void init(){ //記得初始化
sz=last=0;
len[0]=0,link[0]=-1;
}
void insert(char c){ //插入字元
int now=++sz;
len[now]=len[last]+1;
int p=last;
dp[now]=1;
while(~p&&!Next[p][c-'a']){
Next[p][c-'a']=now;
p=link[p];
}
if(p==-1) link[now]=0;
else{
int q=Next[p][c-'a'];
if(len[p]+1==len[q]) link[now]=q;
else{
int clone=++sz;
len[clone]=len[p]+1;
memcpy(Next[clone],Next[q],sizeof(Next[q]));
link[clone]=link[q];
while(~p&&Next[p][c-'a']==q){
Next[p][c-'a']=clone;
p=link[p];
}
link[q]=link[now]=clone;
}
}
last=now;
}
vector<int> g[maxn];
int dfs(int x){ //預處理出每一個節點表示串的出現次數
for(int i:g[x])
dp[x]+=dfs(i);
return dp[x];
}
bool vis[maxn];
int sum[maxn];
int dfs2(int x){ //預處理出每一個節點其子樹的貢獻和
if(vis[x]) return sum[x];vis[x]=1;
for(int i=0;i<26;++i){
int o=Next[x][i];
if(o) sum[x]+=dfs2(o);
}
return sum[x];
}
void out(int x,int k){
if(dp[x]>=k) return; //扣除該節點的貢獻
k-=dp[x];
for(int i=0;i<26;++i){
int o=Next[x][i];
if(!o) continue;
else if(sum[o]<k) k-=sum[o];//如果子節點的貢獻比目前k小,那麼扣除子節點的貢獻
else{ //如果大于,說明目前節點或者目前節點的子樹包括了第k小
printf("%c",'a'+i);
out(o,k);
return ;
}
}
}
void solve(int t,int k){
for(int i=1;i<=sz;++i)
g[link[i]].push_back(i);
dfs(0);
for(int i=0;i<=sz;++i)
sum[i]=t?dp[i]:(dp[i]=1);
dp[0]=sum[0]=0;
if(dfs2(0)<k) return puts("-1"),void();
out(0,k);
}
}
char s[maxn];
int main() {
scanf("%s",s);
int t,k;scanf("%d%d",&t,&k);
sam::init();
int n=strlen(s);
for(int i=0;i<n;++i) sam::insert(s[i]);
sam::solve(t,k);
return 0;
}