首页 > > 程序设计 > C/C++ >

bzoj3998 [ TJOI2015 ] --后缀自动机

2018-06-17 23:19:54来源：未知阅读 ()

题目大意：

对于一个给定长度为N的字符串，求它的第K小子串是什么。

思路：

先对s构造后缀自动机。

令g[x]为x节点代表的字符串个数

当T=0时，g[x]=1

当T=1时，由于link指针将自动机构成了一颗后缀树，所以每个节点的g就是子树中的g之和。

令f[x]为x节点之后有多少种字符串。

f[x]=Σf[next[x][i]]，0<=i<26

按照max_size拓扑排序一遍，然后利用f[x]就可以找出第k小字符串了。

具体看代码

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 500001
int T,i,j,k,n,m,Len[N<<2],Link[N<<2],b[N],Next[N<<2][26],r[N<<2],f[N<<2],g[N<<2],Num,Last,Cur;
char s[N],ans[N];
inline void Insert(int x){
  Cur=++Num;Len[Cur]=Len[Last]+1;g[Cur]=1;
  int p;
  for(p=Last;p&&!Next[p][x];p=Link[p])Next[p][x]=Cur;
  if(!p)Link[Cur]=1;else{
    int q=Next[p][x];
    if(Len[p]+1==Len[q])Link[Cur]=q;else{
      int C=++Num;
      Len[C]=Len[p]+1;Link[C]=Link[q];
      memcpy(Next[C],Next[q],sizeof(Next[q]));
      Link[Cur]=Link[q]=C;
      for(;p&&Next[p][x]==q;p=Link[p])Next[p][x]=C;
    }
  }Last=Cur;
}
inline void Init(bool F){
  for(int i=1;i<=Num;i++)b[Len[i]]++;
  for(int i=1;i<=n;i++)b[i]+=b[i-1];
  for(int i=1;i<=Num;i++)r[b[Len[i]]--]=i;
  for(int i=Num;i;i--){
    int x=r[i];
    if(F)g[Link[x]]+=g[x];else g[x]=1;
  }
  g[1]=0;
  for(int i=Num;i;i--){
    int x=r[i];f[x]=g[x];
    for(int j=0;j<26;j++)f[x]+=f[Next[x][j]];
  }
}
inline void Find(int k){
  if(f[1]<k){printf("-1");return;}
  int i,p=1;
  while(g[p]<k){
    k-=g[p];
    for(i=0;i<26;i++)
      if(f[Next[p][i]]<k)k-=f[Next[p][i]];else break;
    if(i>=26)return;
    putchar(i+'a');
    p=Next[p][i];
  }
}
int main()
{
  scanf("%s",s);
  n=strlen(s);Num=Last=1;
  for(i=0;i<n;i++)Insert(s[i]-'a');
  scanf("%d%d",&T,&k);
  Init(T);
  Find(k);
  return 0;
}