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

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]弦论 解题报告