洛谷 P3975 / loj 2102 [TJOI2015] 弦论 题解【后缀自动机】【拓扑排序】

点击量：217

后缀自动机入门。

目录

题目描述

为了提高智商，ZJY 开始学习弦论。

这一天，她在《String theory》中看到了这样一道问题：对于一个给定的长度为 $ n$ 的字符串,求出它的第 $ k$ 小子串是什么。你能帮帮她吗？

输入输出格式

输入格式：

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

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

输出格式：

输出数据仅有一行，该行有一个字符串，为第 $ k$ 小的子串。如果子串数目不足 $ k$ 个，则输出 $ -1$。

输入输出样例

输入样例：

aabc
0 3

输出样例：

aab

数据范围与约定

对于 $ 10\%$ 的数据，$ n\le 1000$。

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

对于 $ 100\%$ 的数据，$ n\le 5 \times 10^5,\ t<2,\ k\le 10^9$。

题解：

SAM 学习笔记…先鸽一会。

这个题是找出第 $ k$ 大子串。因为在字符串中，第一关键字是字符，而不是长度，所以可以一个字符一个字符的比对。

那么我们先构建出 SAM，如果 $ t=1$，还需要跳 parent 树来计算一个串出现了多少次。记一个状态的贡献为 $ r$。

然后还需要对 SAM 反向拓扑排序/记忆化搜索，得出走这条边可能到达多少种子串，也就是 DAG 后面每一条路径的 $ r$ 之和，记为 $ f$。

然后从起始节点开始检测。每次遍历 a~z，如果发现那条边的 $ f$ 小于 $ k$，那么第 $ k$ 小的不在那边，此时让 $ k$ 减去 $ f$。如果发现 $ f$ 大于 $ k$，则进入这条边。因为我们选了这条边，而后缀自动机的每一个状态都代表了一个子串，因此要把 $ f$ 减去新到点的 $ r$。

如果此时发现 $ k\ge 0$，说明第 $ k$ 小的子串就在刚才那一步的状态里。否则继续在 SAM 上跑。

时间复杂度 $ O(n)$。

Code：

#include<cstdio>
#include<cstring>
struct edge
{
    int n,nxt;
    edge(int n,int nxt)
    {
        this->n=n;
        this->nxt=nxt;
    }
    edge(){}
}e[2000100];
int head[1000100],ecnt=-1;
void add(int from,int to)
{
    e[++ecnt]=edge(to,head[from]);
    head[from]=ecnt;
}
char s[500100];
int ch[26][1000100],mx[1000100],par[1000100],r[1000100],pcnt;
void build()
{
    int p=pcnt=1;
    for(int i=1;s[i]!='\0';++i)
    {
        int w=s[i]-'a';
        int np=++pcnt;
        mx[np]=mx[p]+1;
        r[np]=1;
        while(p&&!ch[w][p])
        {
            ch[w][p]=np;
            p=par[p];
        }
        if(!p)
            par[np]=1;
        else
        {
            int q=ch[w][p];
            if(mx[q]==mx[p]+1)
                par[np]=q;
            else
            {
                int nq=++pcnt;
                mx[nq]=mx[p]+1;
                while(p&&ch[w][p]==q)
                {
                    ch[w][p]=nq;
                    p=par[p];
                }
                for(int j=0;j<26;++j)
                    ch[j][nq]=ch[j][q];
                par[nq]=par[q];
                par[q]=nq;
                par[np]=nq;
            }
        }
        p=np;
    }
}
void dfs(int x)
{
    for(int i=head[x];~i;i=e[i].nxt)
    {
        dfs(e[i].n);
        r[x]+=r[e[i].n];
    }
}
int d[1000100];
int q[1000100],l=0,R=0;
long long f[1000100];
int main()
{
    memset(head,-1,sizeof(head));
    scanf("%s",s+1);
    int t,k;
    scanf("%d%d",&t,&k);
    build();
    for(int i=2;i<=pcnt;++i)
        add(par[i],i);
    if(t)
        dfs(1);
    else
        for(int i=1;i<=pcnt;++i)
            r[i]=1;
    memset(head,-1,sizeof(head));
    ecnt=-1;
    for(int i=1;i<=pcnt;++i)
    {
        int flag=0;
        for(int j=0;j<26;++j)
            if(ch[j][i])
            {
                flag=1;
                ++d[i];
                add(ch[j][i],i);
            }
        if(!flag)
            q[++R]=i;
    }
    while(l<R)
    {
        int x=q[++l];
        f[x]+=r[x];
        for(int i=head[x];~i;i=e[i].nxt)
        {
            f[e[i].n]+=f[x];

            --d[e[i].n];
            if(!d[e[i].n])
                q[++R]=e[i].n;
        }
    }
    t=1;
    while(k>0)
    {
        int flag=0;
        for(int i=0;i<26;++i)
        {
            if(f[ch[i][t]]<k)
                k-=f[ch[i][t]];
            else
            {
                flag=1;
                k-=r[ch[i][t]];
                printf("%c",'a'+i);
                t=ch[i][t];
                break;
            }
        }
        if(!flag)
            break;
    }
    if(k>0)
        puts("-1");
    return 0;
}