您當前位置：首頁 > php開源 > php教程 > 【BZOJ3998】【TJOI2015】弦論后綴自動機

【BZOJ3998】【TJOI2015】弦論后綴自動機

來源：程序員人生發布時間：2015-05-05 08:29:24 閱讀次數：2643次

鏈接：

#include <stdio.h>
int main()
{
    puts("轉載請注明出處[vmurder]謝謝");
    puts("網址：blog.csdn.net/vmurder/article/details/45369569");
}

題解：

首先我們可以建1個后綴自動機。
然后每條路徑走到每一個點都是1個串，它們是有字典序的。
我們只需要統計出往每一個點走以后都有多少串就行了。
$f_i = (sum {f_{son}})+num_i$
對不計重復的情況下， $num_i=1$
對計算重復的情況下，每一個節點都有多種走到最后的方式， $num_i$ 就是看有這個種數。
比如 $ababab$ ， $aba$ 這個串最后可以走成 $abab$ 、 $ababab$ 。因而 $num$ 是2。
初值是所有 $np$ 的 $num=1$ ，然后 $num_i = sum {num_{son}}$ 。

$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;
}