洛谷P3975

Portal

Description

给出一个小写字母串(s(|s|leq5 imes10^5),tin{0,1},k(kleq10^9))，求(s)的第(k)小子串。(t=0)时不同位置的相同子串算作一个，(t=1)时不同位置的相同子串算作多个。

Solution

对(s)建立后缀自动机。(t=1)时统计(cnt[p])表示状态(p)代表的子串的出现次数，也就是(|Right(p)|)；(t=0)时(cnt[p]=1)。然后计算(siz[p]=cnt[p]+sum_{qin ch[p]} siz[q])表示以状态(p)为前缀能延伸出多少子串。(cnt)和(siz)都能自底向上延(parent)树更新。计算出(siz)后就可以通过简单的(DFS)来求出答案串了。

时间复杂度(O(|s|))。

Code

//[TJOI2015]弦论
#include <cstdio>
int const N=1e6+10;
int n,T,k; char s[N];
int ndCnt,rt,last;
int prt[N],ch[N][26],len[N]; int cnt[N];
void ins(int x)
{
    int p=last,np=++ndCnt;
    len[np]=len[p]+1,last=np; cnt[np]=1;
    for(p;p&&!ch[p][x];p=prt[p]) ch[p][x]=np;
    if(!p) {prt[np]=rt; return;}
    int q=ch[p][x];
    if(len[q]==len[p]+1) {prt[np]=q; return;}
    int nq=++ndCnt; len[nq]=len[p]+1;
    for(int i=0;i<26;i++) ch[nq][i]=ch[q][i];
    prt[nq]=prt[q]; prt[q]=prt[np]=nq;
    for(p;ch[p][x]==q;p=prt[p]) ch[p][x]=nq;
}
void buildSAM(char s[])
{
    last=rt=++ndCnt;
    for(int i=1;s[i];i++) ins(s[i]-'a');
}
int cnt0[N],ord[N]; int siz[N];
void getSiz()
{
    for(int i=1;i<=ndCnt;i++) cnt0[len[i]]++;
    for(int i=ndCnt-1;i>=0;i--) cnt0[i]+=cnt0[i+1];
    for(int i=ndCnt;i>=1;i--) ord[cnt0[len[i]]--]=i;
    if(T==0) for(int i=1;i<=ndCnt;i++) cnt[i]=1;
    else
        for(int i=1;i<=ndCnt;i++)
        {
            int p=ord[i];
            if(prt[p]) cnt[prt[p]]+=cnt[p];
        }
    cnt[rt]=0;
    for(int i=1;i<=ndCnt;i++)
    {
        int p=ord[i]; siz[p]=cnt[p];
        for(int x=0;x<26;x++) siz[p]+=siz[ch[p][x]];
    }
}
char ans[N];
bool dfs(int p,int x,int k)
{
    if(k<=cnt[p]) return true;
    k-=cnt[p];
    for(int i=0;i<26;i++)
    {
        int q=ch[p][i];
        if(k>siz[q]) {k-=siz[q]; continue;}
        ans[x]=i+'a'; return dfs(q,x+1,k);
    }
    return false;
}
int main()
{
    scanf("%s",s+1); scanf("%d%d",&T,&k);
    buildSAM(s); getSiz();
    if(dfs(rt,1,k)) puts(ans+1);
    else puts("-1");
    return 0;
}

P.S.

%%%Pickupwin
白天与巨佬谈笑风生，回家一个人总结题解，岂不美哉？