BZOJ 2894: 世界线广义后缀自动机

Description

由于春希对于第二世代操作的不熟练，所以刚使用完invasion process便掉落到了世界线之外，错综复杂的平行世界信息涌入到春希的意识中。春希明白了事件的真相。

在一个冬马与雪菜同时存在的世界里，傲娇的冬马最终还是博得了春希的内心。然而看着好友雪菜的消瘦，内心愧疚的冬马启动了第二世代操作，想找到一个雪菜最终成功的世界，却发现哪里都没有。绝望的冬马决定耗尽自己全部的第二世代操作点数，自创一个没有自己只有雪菜与春希的世界。

虽然这个世界一开始效果很好，春希与雪菜很快的被命运撮合在了一起，然而没有了冬马的雪菜，如没有了大海的沙滩，失去了傍依。

虽然世界里没有冬马的存在，但是由于冬马创造时的疏忽，这个世界里的雪菜依然存在着因独占春希而产生的对冬马的愧疚感，这种愧疚感折磨着雪菜，最终雪菜选择了自毁忘记春希。

看着这一切的春希深知不管是三个人一起的快乐，还是两个人独处的甜蜜，都无法消除冬马与雪菜内心的自责，无论如何修改世界，三人都只会更加痛苦，于是春希使用了自己剩余的全部操作点数，念出了key world:WhiteAlbum2，开始了initialization process.

在initialization process中，春希需要整理世界线，才能回归原本的世界。

世界线是一棵根节点为1的树，每个节点为1个字符。规定树上的子串为从某个节点（不一定是1号节点）出发往其子节点走所形成的字符串。每一个子串相当于一个平行世界，要想重构世界，就需要知道两个信息：

1. 不同子串的个数

2. 将不同的子串排序后，字典序第k-1小的子串。

如图所示为一个世界线的样例，从4->5的子串为bb,1->5的为abb

Input

第一行两个整数n，q表示节点个数以及询问个数

第二行n个字符，表示编号为i的字符是什么。

接下来n-1行表示一棵树。

接下来q行，每行一个整数k

Output

第一行为不同支付串个数。

接下来q行为q个询问的答案(注意输出的是第k-1小的子串，如果K=1请直接换行)，如果不存在（不包括k=1）输出-1.

题解：广义后缀自动机查询字典序第 $k$ 小，直接维护 $sumv[x]$ 表示以 $x$ 为根后面子串的个数，$dfs$ 一遍即可.

#include<bits/stdc++.h>

#define maxn 300000

#define ll long long

using namespace std;

vector<int>G[maxn];

char str[maxn];

int n,Q;

ll ans=1;

void setIO(string s)

{

    string in=s+".in";

    string out=s+".out";

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

    freopen(out.c_str(),"w",stdout);

}

namespace SAM

{

    int tot;

    int ch[maxn<<1][28], f[maxn<<1], len[maxn<<1], cnt[maxn<<1], sumv[maxn<<1], C[maxn<<1], rk[maxn<<1];

    char tr[maxn];

    void init()

    {

        tot=1;

    }

    int extend(int c,int last)

    {

        int p=last;

        if(!ch[p][c])

        {

            int np=++tot;

            last=np, len[np]=len[p]+1;

            while(p&&!ch[p][c])ch[p][c]=np,p=f[p];

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

            else

            {

                int q=ch[p][c];

                if(len[q]==len[p]+1)  f[np]=q;

                else

                {

                    int nq=++tot;

                    len[nq]=len[p]+1;

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

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

                    while(p&&ch[p][c]==q) ch[p][c]=nq, p=f[p];

                }

            }

            ans+=len[np]-len[f[np]];

        }

        else

        {

            int q=ch[p][c];

            if(len[q]==len[p]+1) last=q;

            else

            {

                int nq=++tot;

                len[nq]=len[p]+1;

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

                f[nq]=f[q], f[q]=nq;

                while(p&&ch[p][c]==q) ch[p][c]=nq,p=f[p];

                last=nq;

            }

        }

        return last;

    }

    void Get()

    {

        for(int i=1;i<=tot;++i) ++C[len[i]];

        for(int i=1;i<=tot;++i) C[i]+=C[i-1];

        for(int i=1;i<=tot;++i) rk[C[len[i]]--]=i;

        for(int i=tot;i>=1;--i)

        {

            int p=rk[i];

            sumv[p]=1;

            for(int j=0;j<26;++j) if(ch[p][j]) sumv[p]+=sumv[ch[p][j]];

        }

    }

    void solve(int k)

    {

        int cur=1,cc=0,flag2=1;

        while(flag2 && cur)

        {

            flag2=0;

            if(cur!=1) k-=1;

            if(k<=0)

            {

                for(int i=1;i<=cc;++i) printf("%c",tr[i]);

                puts("");

                return;

            }

            for(int i=0;i<27;++i)

            {

                if(ch[cur][i])

                {

                    if(sumv[ch[cur][i]] >= k)

                    {

                        cur=ch[cur][i];

                        tr[++cc]=i+'a';

                        flag2=1;

                        break;

                    }

                    else k-=sumv[ch[cur][i]];

                }

            }

        }

        puts("-1");

    }

};

void DFS(int u,int fa,int cur)

{

    cur=SAM::extend(str[u]-'a',cur);   // 插入该字符后的状态

    for(int i=0;i<G[u].size();++i)

    {

        int v=G[u][i];

        if(v==fa) continue;

        DFS(v,u,cur);

    }

}

int main()

{

    // setIO("input");

    scanf("%d%d",&n,&Q);

    scanf("%s",str+1);

    for(int i=1,a,b;i<n;++i)

    {

        scanf("%d%d",&a,&b);

        G[a].push_back(b);

        G[b].push_back(a);

    }

    SAM::init();

    DFS(1,0,1);

    SAM::Get();

    printf("%lld",ans);

    puts("");

    while(Q--)

    {

        int k;

        scanf("%d",&k); --k;

        if(k) SAM::solve(k);

        else puts("");

    }

    return 0;

}

世界