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 <cstdio>

#include <cstring>

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]<k) return puts("-1"),0;

    int now=1;

    while(k>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

弦论

洛谷 P3975 [TJOI2015]弦论 解题报告