正文概述

链接：

#include <stdio.h>

int main()

{

    puts("转载请注明出处[vmurder]谢谢");

    puts("网址：blog.csdn.net/vmurder/article/details/45369569");

}

题解：

首先我们可以建1个后缀自动机。
然后每条路径走到每一个点都是1个串，它们是有字典序的。
我们只需要统计出往每一个点走以后都有多少串就行了。
fi=(∑fson)+numi
对不计重复的情况下，numi=1
对计算重复的情况下，每一个节点都有多种走到最后的方式，numi 就是看有这个种数。
比如 ababab，aba 这个串最后可以走成 abab、ababab 。因而 num 是2。
初值是所有 np 的 num=1 ，然后 numi=∑numson 。

f函数处理出来以后，就随意弄了。
每次往下走就好了，类似26分?　(雾
无妨看我的 dfs 函数。

代码：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 1001000

#define T 26

#define inf 0x3f3f3f3f

using namespace std;

struct SAM

{

    int son[N][T],pa[N],dep[N],last,cnt;

    int val[N],f[N];

    void init(){last=cnt=1;}

    int newnode(int p){dep[++cnt]=dep[p]+1;return cnt;}

    void add(int x)

    {

        int p=last;

        int np=newnode(p);

        while(p&&!son[p][x])son[p][x]=np,p=pa[p];

        if(!p)pa[np]=1;

        else {

            int q=son[p][x];

            if(dep[q]==dep[p]+1)pa[np]=q;

            else {

                int nq=newnode(p);

                pa[nq]=pa[q],pa[q]=pa[np]=nq;

                memcpy(son[nq],son[q],sizeof son[q]);

                while(p&&son[p][x]==q)son[p][x]=nq,p=pa[p];

            }

        }

        val[last=np]=1;

    }

    int d[N],stk[N],top;

    struct Eli

    {

        int v,next;

    }e[N*T/5];

    int head[N],ct;

    void add(int u,int v)

    {

        d[v]++;

        e[++ct].v=v;

        e[ct].next=head[u];

        head[u]=ct;

    }

    void bfsf()

    {

        int i,j,u,v;

        for(i=1;i<=cnt;i++)for(j=0;j<T;j++)if(son[i][j])

                add(son[i][j],i);

        for(i=1;i<=cnt;i++)if(!d[i])stk[++top]=i;

        while(top)

        {

            u=stk[top--],f[u]++,val[u]=1;

            for(i=head[u];i;i=e[i].next)

            {

                v=e[i].v,f[v]+=f[u];

                if(!--d[v])stk[++top]=v;

            }

        }

        f[1]--;

    }

    void bfsg()

    {

        int i,j,u,v;

        for(i=2;i<=cnt;i++)d[pa[i]]++;

        for(i=1;i<=cnt;i++)if(!d[i])stk[++top]=i;

        while(top)

        {

            u=stk[top--];

            val[pa[u]]+=val[u];

            if(!--d[pa[u]])stk[++top]=pa[u];

        }

        for(i=1;i<=cnt;i++)for(j=0;j<T;j++)

            if(son[i][j])add(son[i][j],i);

        for(i=1;i<=cnt;i++)if(!d[i])stk[++top]=i;

        while(top)

        {

            u=stk[top--],f[u]+=val[u];

            for(i=head[u];i;i=e[i].next)

            {

                v=e[i].v,f[v]+=f[u];

                if(!--d[v])stk[++top]=v;

            }

        }

        f[1]-=val[1];

    }

    void dfs(int x,int k)

    {

        int i,v;

        for(i=0;i<T;i++)if(v=son[x][i])

        {

            if(k<=f[v])

            {

                printf("%c",'a'+i);

                k-=val[v];

                if(k>0)dfs(v,k);

                return ;

            }

            else k-=f[v];

        }

    }

}sam;

char s[N/2];

int main()

{

    freopen("test.in","r",stdin);

    int i,j,k;

scanf("%s",s+1); sam.init(); for(i=1;s[i];i++)sam.add(s[i]-'a'); scanf("%d%d",&j,&k); if(j==0)sam.bfsf(); else sam.bfsg(); sam.dfs(1,k); return 0; }

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，您必须在下载后24小时内删除！
3. 不得使用于非法商业用途，不得违反国家法律。否则后果自负！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 本站源码并不保证全部能正常使用，仅供有技术基础的人学习研究，请谨慎下载
8. 如遇到加密压缩包，请使用WINRAR解压,如遇到无法解压的请联系管理员！

波比源码 » 【BZOJ3998】【TJOI2015】弦论后缀自动机

分享到：