弦论 bzoj-3998 TJOI-2015

题目大意：给定一个字符串，求其$k$小子串。

注释：$1\le length \le 5\cdot 10^5$，$1\le k\le 10^9$。

想法：

后缀数组傻逼题。

初学后缀自动机我们尝试用后缀自动机解决。

首先先建出$SAM$。

分别考虑$T=0$和$T=1$的情况。

我们处理$f$数组表示以当前节点代表的字符串为前缀的子串个数。

它们俩之间的区别就是$Right$集合的大小。

详情看代码把。

代码：

#include <bits/stdc++.h>

#define N 1000010

using namespace std;

int n,opt,nxt[N][26],fa[N],dis[N],lst=1,cnt=1,v[N],q[N],Right[N],f[N];

char str[N];

void update(int c)

{

    int p=lst,np=lst=++cnt;

    dis[np]=dis[p]+1; Right[np]=1;

    while(p&&!nxt[p][c]) nxt[p][c]=np,p=fa[p];

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

    else

    {

        int q=nxt[p][c];

        if(dis[q]==dis[p]+1) fa[np]=q;

        else

        {

            int nq=++cnt;

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

            dis[nq]=dis[p]+1; fa[nq]=fa[q]; fa[np]=fa[q]=nq;

            while(p&&nxt[p][c]==q) nxt[p][c]=nq,p=fa[p];

        }

    }

}

void init()

{

    for(int i=1;i<=cnt;i++) v[dis[i]]++;

    for(int i=1;i<=n;i++) v[i]+=v[i-1];

    for(int i=cnt;i;i--) q[v[dis[i]]--]=i;

    for(int i=cnt;i;i--)

    {

        int t=q[i];

        if(opt) Right[fa[t]]+=Right[t];

        else Right[t]=1;

    }

    Right[1]=0; for(int i=cnt;i;i--)

    {

        int t=q[i]; f[t]=Right[t];

        for(int j=0;j<26;j++) f[t]+=f[nxt[t][j]];

    }

}

void query(int p,int k)

{

    if(k<=Right[p]) return;

    k-=Right[p];

    for(int i=0;i<26;i++) if(nxt[p][i])

    {

        if(k<=f[nxt[p][i]])

        {

            putchar(i+'a'); query(nxt[p][i],k);

            return;

        }

        k-=f[nxt[p][i]];

    }

}

int main()

{

    int k; scanf("%s%d%d",str+1,&opt,&k); n=strlen(str+1);

    for(int i=1;i<=n;i++) update(str[i]-'a');

    init();

    if(k>f[1]) puts("-1");

    else query(1,k);

    return 0;

}

小结：后缀自动机搭配其他的数据结构的时候会比较有用，但是感觉后缀数组更好写啊$qwq$......

巴特西

[bzoj3998][TJOI2015]弦论_后缀自动机

弦论 bzoj-3998 TJOI-2015

最新文章

热门文章