BZOJ 3998: [TJOI2015]弦论 [后缀自动机 DP]

3998: [TJOI2015]弦论

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 2152  Solved: 716
[Submit][Status][Discuss]

Description

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

Input

第一行是一个仅由小写英文字母构成的字符串S

第二行为两个整数T和K，T为0则表示不同位置的相同子串算作一个。T=1则表示不同位置的相同子串算作多个。K的意义如题所述。

Output

输出仅一行，为一个数字串，为第K小的子串。如果子串数目不足K个，则输出-1

---

T=1和上一题一样

T=2的话，每个状态不是代表一个子串，而是代表|Right|个子串，然后一样了

判断无解也可以直接与sum[root]比较哦

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <map>

using namespace std;

const int N=1e6+;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n,Type,k;

int c[N],a[N],d[N],sum[N];

char s[N];

struct State{

    int ch[],par,val;

}t[N];

int sz,root,last;

inline int nw(int _){t[++sz].val=_;return sz;}

inline void iniSAM(){sz=;root=last=nw();}

void extend(int c){

    int p=last,np=nw(t[p].val+);d[np]=;

    for(;p&&!t[p].ch[c];p=t[p].par) t[p].ch[c]=np;

    if(!p) t[np].par=root;

    else{

        int q=t[p].ch[c];

        if(t[q].val==t[p].val+) t[np].par=q;

        else{

            int nq=nw(t[p].val+);

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

            t[nq].par=t[q].par;

            t[q].par=t[np].par=nq;

            for(;p&&t[p].ch[c]==q;p=t[p].par) t[p].ch[c]=nq;

        }

    }

    last=np;

}

void RadixSort(){

    for(int i=;i<=sz;i++) c[t[i].val]++;

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

    for(int i=;i<=sz;i++) a[c[t[i].val]--]=i;

}

void dp(){

    RadixSort();

    for(int i=sz;i>=;i--){

        int u=a[i];

        if(Type==) d[t[u].par]+=d[u];

        else d[u]=;

    }

    for(int i=sz;i>=;i--){

        int u=a[i];

        sum[u]=d[u];

        for(int j=;j<;j++) sum[u]+=sum[t[u].ch[j]];

    }

}

int ans[N],p;

void kth(int k){

    int u=root;

    while(k>){

        for(int i=;i<;i++) if(t[u].ch[i]){

            int v=t[u].ch[i];

            if(sum[v]>=k) {ans[++p]=i;k-=d[v];u=v;break;}

            else k-=sum[v];

        }

    }

}

int main(){

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

    scanf("%s",s+);

    n=strlen(s+);

    iniSAM();

    for(int i=;i<=n;i++) extend(s[i]-'a');

    Type=read();k=read();

    dp();

    if(sum[]<k) puts("-1");

    else{

        kth(k);

        for(int i=;i<=p;i++) putchar(ans[i]+'a');

    }

}