낙곡P3975[천진성선2015](접미사 자동기DP)

제목 링크

문제풀이

AC 코드

#include
#include
#include
using namespace std;
const int NN=5e5+10;
struct NODE
{
    int ch[26];
    int len,fa;
    NODE(){memset(ch,0,sizeof(ch));len=0;}
}dian[NN<<1];
int is_pre[NN<<1];//       
int las=1,tot=1;
void add(int c)
{
    int p=las;int np=las=++tot;
    is_pre[np]=1;//endpos[np]={i} where s[i]=c
    dian[np].len=dian[p].len+1;
    for(;p&&!dian[p].ch[c];p=dian[p].fa)dian[p].ch[c]=np;
    if(!p){dian[np].fa=1;}//   case 1
    else
    {
        int q=dian[p].ch[c];
        if(dian[q].len==dian[p].len+1)dian[np].fa=q;//   case 2
        else
        {
            int nq=++tot;dian[nq]=dian[q];//endpos  i 
            dian[nq].len=dian[p].len+1;
            dian[q].fa=dian[np].fa=nq; 
            for(;p&&dian[p].ch[c]==q;p=dian[p].fa)dian[p].ch[c]=nq;//   case 3
        }
    }
}
int n;
vector<int>parentcon[NN<<1];
char s[NN];
void sam(){
    las=1,tot=1;
    for(int i=1;i<(n<<1);i++)is_pre[i]=0;
    for(int i=1;i<=n;i++)add(s[i]-'a');
    for(int i=1;i<=tot;i++){
        parentcon[dian[i].fa].push_back(i);
    }
}
long long endpos[NN<<1],dp[NN<<1];
void get_endpos(int cur,int fa){
    int up=parentcon[cur].size();
    endpos[cur]=is_pre[cur];
    for(int i=0;i<up;i++){
        int nex=parentcon[cur][i];
        if(nex!=fa){
            get_endpos(nex,fa);
            endpos[cur]+=endpos[nex];
        }
    }
}
void get_num(int cur){//   
    if(dp[cur])return;
    dp[cur]=0;
    for(int i=0;i<26;i++){
        int nex=dian[cur].ch[i];
        if(nex){
            get_num(nex);
            dp[cur]+=dp[nex]+endpos[nex];//dp[nex] i+xxx   ,endpos[nex] i   ,dp    
        }
    }
}
void get_num_dif(int cur){//    
    if(dp[cur])return;
    dp[cur]=1;//   
    for(int i=0;i<26;i++){
        int nex=dian[cur].ch[i];
        if(nex){
            get_num_dif(nex);
            dp[cur]+=dp[nex];
        }
    }
}
int ans[NN],anslen;
int t;
int dfs(int cur,int k,int deep){
    if(k<=0){anslen=deep-1;return k;}
    for(int i=0;i<26;i++){
        int nex=dian[cur].ch[i];
        if(nex){
            int simp=(t?endpos[nex]:1);
            if(dp[nex]+simp>=k){
                ans[deep]=i;
                return dfs(nex,k-simp,deep+1);
                break;
            }
            else{
                k-=(dp[nex]+simp);
            }
        }
    }
    return k;
}

int len;
int main()
{

    scanf("%s",s+1);n=strlen(s+1);
    sam();
    int k;
    scanf("%d%d",&t,&k);
    memset(dp,0,sizeof(dp));
    memset(endpos,0,sizeof(endpos));
    if(t==1){
        get_endpos(1,0);
        get_num(1);
        if(k>dp[1])printf("-1
");
        else{
            dfs(1,k,1);
            for(int i=1;i<=anslen;i++)printf("%c",ans[i]+'a');
            printf("
");
        }
    }
    else{
        get_num_dif(1);
        for(int i=1;i<=tot;i++)dp[i]--;//   
        if(k>dp[1])printf("-1
");
        else{
            dfs(1,k,1);
            for(int i=1;i<=anslen;i++)printf("%c",ans[i]+'a');
            printf("
");
        }

    }
    return 0;
}