P3975 [TJOI2015]弦论

题目描述

为了提高智商,ZJY开始学习弦论。这一天,她在《String theory》中看到了这样一道问题:对于一个给定的长度为\(n\)的字符串,求出它的第\(k\)小子串是什么。你能帮帮她吗?

输入输出格式

输入格式：

第一行是一个仅由小写英文字母构成的字符串\(s\)

第二行为两个整数\(t\)和\(k\),\(t\)为\(0\)则表示不同位置的相同子串算作一个,\(t\)为\(1\)则表示不同位置的相同子串算作多个。\(k\)的意义见题目描述。

输出格式：

输出数据仅有一行,该行有一个字符串,为第\(k\)小的子串。若子串数目不足\(k\)个,则输出\(-1\)。

说明

数据范围

对于\(10\%\)的数据，\(n ≤ 1000\)。

对于\(50\%\)的数据，\(t = 0\)。

对于\(100\%\)的数据，\(n ≤ 5 × 10^5, t < 2, k ≤ 10^9\)。

---

建立后缀自动机，按要求统计每个状态的贡献。

然后在自动机上（非par树）统计一下后缀数量，根据后缀数量进入后面的节点，得到的一条路径即为答案

---

Code:

#include 
    
     #include 
     
      const int N=1e6+10;char s[N];int t,k,n,tax[N],A[N];int len[N],ch[N][26],siz[N],par[N],sum[N],tot=1,las=1;void extend(int c){    int now=++tot,p=las;    len[now]=len[p]+1,siz[now]=1;    while(p&&!ch[p][c]) ch[p][c]=now,p=par[p];    if(!p) par[now]=1;    else    {        int x=ch[p][c];        if(len[x]==len[p]+1) par[now]=x;        else        {            int y=++tot;            len[y]=len[p]+1,par[y]=par[x];            memcpy(ch[y],ch[x],sizeof ch[x]);            while(p&&ch[p][c]==x) ch[p][c]=y,p=par[p];            par[now]=par[x]=y;        }    }    las=now;}int main(){    scanf("%s%d%d",s+1,&t,&k);    n=strlen(s+1);    for(int i=1;i<=n;i++) extend(s[i]-'a');    for(int i=1;i<=tot;i++) ++tax[len[i]];    for(int i=1;i<=n;i++) tax[i]+=tax[i-1];    for(int i=1;i<=tot;i++) A[tax[len[i]]--]=i;    for(int i=tot;i;i--)    {        if(t) siz[par[A[i]]]+=siz[A[i]];        else siz[A[i]]=1;    }    siz[1]=0;    for(int i=tot;i;i--)    {        sum[A[i]]=siz[A[i]];        for(int c=0;c<26;c++)            sum[A[i]]+=sum[ch[A[i]][c]];    }    if(sum[1]
      
       0)    {        int c=0;        while(k>sum[ch[now][c]]) k-=sum[ch[now][c++]];        putchar(c+'a');        now=ch[now][c];        k-=siz[now];    }    return 0;}
      
     
    

---

2019.1.7