BZOJ3998: [TJOI2015]弦论（后缀自动机，Parent树）

Description

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

Input

第一行是一个仅由小写英文字母构成的字符串S

第二行为两个整数T和K，T为0则表示不同位置的相同子串算作一个。T=1则表示不同位置的相同子串算作多个。K的意义如题所述。

Output

输出仅一行，为一个数字串，为第K小的子串。如果子串数目不足K个，则输出-1

Sample Input

aabc
0 3

Sample Output

aab

解题思路：

在后缀自动机Parent树上的每个节点所代表的串都是以祖先节点为后缀的逆序子串。

利用这一性质我们可以很方便地求解一个子串出现多少次的问题(其子树内实点数）

那么这道题是求解排名的问题。

一个后缀自动机可以识别一个串所有后缀。

若按前缀查询，就是所有字串，字串出现次数和就是其母串次数和的累加。

当 t=0 时，认为其实点只有自己记录。

而 t=1时，认为其子节点被记录。

累加其sum值作为以此值为前缀的串个数。

最后相减逼近答案输出即可。

代码：

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 typedef long long lnt;
  5 struct sant{
  6     int tranc[26];
  7     int len;
  8     int pre;
  9 }s[1000000];
 10 struct pnt{
 11     lnt sum;
 12     lnt size;
 13 }p[1000000];
 14 int siz;
 15 int fin;
 16 int n,t;
 17 lnt k;
 18 char tmp[1000000];
 19 int has[1000000];
 20 int topo[1000000];
 21 void Insert(int c)
 22 {
 23     int nwp,nwq,lsp,lsq;
 24     nwp=++siz;
 25     s[nwp].len=s[fin].len+1;
 26     p[nwp].size=1;
 27     for(lsp=fin;lsp&&!s[lsp].tranc[c];lsp=s[lsp].pre)
 28         s[lsp].tranc[c]=nwp;
 29     if(!s[lsp].tranc[c])
 30         s[nwp].pre=1;
 31     else{
 32         lsq=s[lsp].tranc[c];
 33         if(s[lsq].len==s[lsp].len+1)
 34             s[nwp].pre=lsq;
 35         else{
 36             nwq=++siz;
 37             s[nwq]=s[lsq];
 38             s[nwq].len=s[lsp].len+1;
 39             s[nwp].pre=s[lsq].pre=nwq;
 40             while(s[lsp].tranc[c]==lsq)
 41             {
 42                 s[lsp].tranc[c]=nwq;
 43                 lsp=s[lsp].pre;
 44             }
 45         }
 46     }
 47     fin=nwp;
 48     return ;
 49 }
 50 int main()
 51 {
 52     fin=siz=1;
 53     scanf("%s",tmp+1);
 54     scanf("%d%lld",&t,&k);
 55     n=strlen(tmp+1);
 56     for(int i=1;i<=n;i++)
 57         Insert(tmp[i]-'a');
 58     for(int i=1;i<=siz;i++)
 59         has[s[i].len]++;
 60     for(int i=1;i<=siz;i++)
 61         has[i]+=has[i-1];
 62     for(int i=1;i<=siz;i++)
 63         topo[has[s[i].len]--]=i;
 64     for(int i=siz;i;i--)
 65         if(t)
 66             p[s[topo[i]].pre].size+=p[topo[i]].size;
 67         else
 68             p[topo[i]].size=1;
 69     p[1].size=0;
 70     for(int i=siz;i;i--)
 71     {
 72         int h=topo[i];
 73         p[h].sum=p[h].size;
 74         for(int c=0;c<26;c++)
 75             if(s[h].tranc[c])
 76                 p[h].sum+=p[s[h].tranc[c]].sum;
 77     }
 78     if(k>p[1].sum)
 79     {
 80         puts("-1");
 81         return 0;
 82     }
 83     int root=1;
 84     while(k>0)
 85     {
 86         for(int c=0;c<26;c++)
 87         {
 88             int l=s[root].tranc[c];
 89             if(!l)continue;
 90             if(k>p[l].sum)
 91                 k-=p[l].sum;
 92             else{
 93                 putchar('a'+c);
 94                 root=s[root].tranc[c];
 95                 k-=p[root].size;
 96                 break;
 97             }
 98         }
 99     }
100     return 0;
101 }