BZOJ 3998 [TJOI2015] 弦论

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3998

题意：对于一个给定长度为 N 的字符串，求它的第 K 小子串是什么。

本质相同与否的子串算不算一个其实只影响了 SAM 上 right 集合大小的含义。

直接建 SAM，拓扑 DP 一下，从根开始贪心的 dfs 即可。

发现拓扑序即按照 mx 排序，可以大幅优化常数。一号板子题。

#include <cmath>
#include <queue>
#include <cstdio>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 500010
#define ll long long
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char s[N];
int T,k;
namespace SAM
{
    #define MAXN 1000010
    int ch[MAXN][26],fail[MAXN];
    int mx[MAXN],val[MAXN],sum[MAXN];//val right大小
    int last=1,tot=1,rt=1;
    int ord[MAXN],bin[MAXN];

    void add(int x)
    {
        int p=last,np=++tot,q,nq;
        last=np,mx[np]=mx[p]+1,val[np]=1;
        while(p&&!ch[p][x])ch[p][x]=np,p=fail[p];
        if(p==0){fail[np]=rt;return ;}
        q=ch[p][x];
        if(mx[q]==mx[p]+1){fail[np]=q;return ;}
        nq=++tot,mx[nq]=mx[p]+1;
        memcpy(ch[nq],ch[q],sizeof(ch[q]));
        fail[nq]=fail[q],fail[np]=fail[q]=nq;
        while(p&&ch[p][x]==q)ch[p][x]=nq,p=fail[p];
    }

    void count()
    {
        for(int i=1;i<=tot;i++)bin[mx[i]]++;
        for(int i=1;i<=tot;i++)bin[i]+=bin[i-1];
        for(int i=tot;i;i--)ord[bin[mx[i]]--]=i;

        for(int i=tot;i;i--)
        {
            int x=ord[i];
            if(T)val[fail[x]]+=val[x];
            else val[x]=1;
        }
        val[1]=0;
        for(int i=tot;i;i--)
        {
            int x=ord[i];
            sum[x]=val[x];
            for(int j=0;j<26;j++)
            sum[x]+=sum[ch[x][j]];
        }
    }

    void dfs(int x,int k)
    {
        if(k<=val[x])return ;
        k-=val[x];
        for(int i=0;i<26;i++)
        if(ch[x][i])
        {
            int to=ch[x][i];
            if(k<=sum[to])
            {
                putchar(i+'a');
                dfs(to,k);
                return ;
            }
            k-=sum[to];
        }
    }
}
int main()
{
    scanf("%s",s+1);
    int n=strlen(s+1);
    for(int i=1;i<=n;i++)
    SAM::add(s[i]-'a');
    T=read(),k=read();
    SAM::count();
    if(k>SAM::sum[1])puts("-1");
    else SAM::dfs(1,k);
}

#include <cmath>

#include <queue>

#include <cstdio>

#include <iomanip>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 500010

#define ll long long

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

char s[N];

int T,k;

namespace SAM

{

#define MAXN 1000010

int ch[MAXN][26],fail[MAXN];

int mx[MAXN],val[MAXN],sum[MAXN];//val right大小

int last=1,tot=1,rt=1;

int ord[MAXN],bin[MAXN];

void add(int x)

{

int p=last,np=++tot,q,nq;

last=np,mx[np]=mx[p]+1,val[np]=1;

while(p&&!ch[p][x])ch[p][x]=np,p=fail[p];

if(p==0){fail[np]=rt;return ;}

q=ch[p][x];

if(mx[q]==mx[p]+1){fail[np]=q;return ;}

nq=++tot,mx[nq]=mx[p]+1;

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

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

while(p&&ch[p][x]==q)ch[p][x]=nq,p=fail[p];

}

void count()

{

for(int i=1;i<=tot;i++)bin[mx[i]]++;

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

for(int i=tot;i;i--)ord[bin[mx[i]]--]=i;

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

{

int x=ord[i];

if(T)val[fail[x]]+=val[x];

else val[x]=1;

}

val[1]=0;

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

{

int x=ord[i];

sum[x]=val[x];

for(int j=0;j<26;j++)

sum[x]+=sum[ch[x][j]];

}

void dfs(int x,int k)

{

if(k<=val[x])return ;

k-=val[x];

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

if(ch[x][i])

{

int to=ch[x][i];

if(k<=sum[to])

{

putchar(i+'a');

dfs(to,k);

return ;

}

k-=sum[to];

}

int main()

{

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

int n=strlen(s+1);

for(int i=1;i<=n;i++)

SAM::add(s[i]-'a');

T=read(),k=read();

SAM::count();

if(k>SAM::sum[1])puts("-1");

else SAM::dfs(1,k);

}

zgz233

zgz233

BZOJ 3998 [TJOI2015] 弦论

l1ll5

Comments | NOTHING