[SAM][dp][拓扑排序][模板] 洛谷 P3975 TJOI2015 弦论

题目链接

题意：

给定一个长度为 n 的字符串，让求出它的第 $k$ 小子串是什么。每次除字符串之外还会给定两个参数 $t $和 $k$ ，$t$ 为 $0$ 则表示不同位置的相同子串算作一个, $t$ 为 $1$ 则表示不同位置的相同子串算作多个。数据范围 $n\le 5*10^5$ $t\in {0,1}$ , $k \le 10^9$.

题解：

后缀自动机板子题。我们知道每一个子串放在sam上跑一定可以走到一个合法节点，反过来说任意一个节点一定代表了一批能走到这儿的子串。那么我们可以想办法把到达每个节点有多少种子串用dag图上dp的方式求出来，然后在t=1的时候，根据sam的性质，给每个dp值再乘以一个 $|endpos|$ 就可以了。学习到的是比我原来板子更快的拓扑排序方式。。。直接用len结果在数组里排序，比起用queue来常数小了很多。另外还纠正了自己的对于sam拓扑序的一个错误认识，他其实无论是slink还是dwag的拓扑序都是一样的，因为无论哪种都一定是从小的子串往大的走。

wa点：

• 拓扑排序之后Sort的内容是从后往前的，注意枚举的时候要反过来。
• 是否是前缀的标记，原来的写法注释是错的，更新了板子。

#include<bits/stdc++.h>

#define CHAR 26
#define nullptr 0
using namespace std;
typedef long long ll;
const int maxn=5e5+5;
const int debug=0;

struct sam_node{
    sam_node* fa,*nxt[CHAR];//fa is slink...
    int len;//max len
    bool flag;
    void clear(){
        fa=nullptr;
        flag=0;
        memset(nxt,0,sizeof(nxt));
    }
    int hmn(){return len-fa->len;}
}pool[maxn<<1];

sam_node *root,*tail;

sam_node* newnode(int len){
    sam_node* cur=tail++;
    cur->clear();
    cur->len=len;
    return cur;
}

void sam_init(){
    tail=pool;
    root=newnode(0);
}

sam_node * extend(sam_node* last,int x){
    sam_node* p=last,*np=newnode(p->len+1);
    while(p&&p->nxt[x]==nullptr)
        p->nxt[x]=np,p=p->fa;
    if(p==nullptr)
        np->fa=root;
    else{
        sam_node* q=p->nxt[x];
        if(q->len==p->len+1)
            np->fa=q;
        else{
            sam_node* nq=newnode(p->len+1);
            memcpy(nq->nxt,q->nxt,sizeof(q->nxt));
            nq->fa=q->fa;
            q->fa=np->fa=nq;
            while(p!=nullptr&&p->nxt[x]==q)
                p->nxt[x]=nq,p=p->fa;
        }
    }
    np->flag=1;
    return np;
}

int Len,ssz;
char ori[maxn];
sam_node* End[maxn];

void build(){
    Len=strlen(ori);
    sam_init();
    sam_node* pre=root,*cr;
    End[0]=root;
    for(int i=1;i<=Len;++i) End[i]=extend(End[i-1],ori[i-1]-'a');
    ssz=tail-pool;
    //debug
    // if(debug){
    //     cout<<"Debug build\n";
    //     sam_node *cur=root;
    //     cout<<ssz<<endl;
    //     for(int i=0;i<ssz;++i){
    //         for(int j=0;j<CHAR;++j){
    //             if((cur+i)->nxt[j]!=nullptr)
    //                 cout<<i<<" "<<(char)(j+'a')<<" "<<((cur+i)->nxt[j]-pool)<<endl;
    //         }
    //     }
    // }
}

//Topsort from ssz to 0 ,both for slink and dwag
int topsort[maxn<<1],ctp[maxn];
void Topsort(){
    for(int i=0;i<=Len;++i) ctp[i]=0;
    for(int i=0;i<ssz;++i) ctp[pool[i].len]++;
    for(int i=1;i<=Len;++i) ctp[i]+=ctp[i-1];//?
    for(int i=ssz-1;i>=0;i--) topsort[--ctp[pool[i].len]]=i;
}

//Get |endpos|
int endpos[maxn<<1];
void getEndpos(int op){
    if(op==0){
        for(int i=0;i<ssz;++i) endpos[i]=1;
        return ;
    }
    sam_node* cur;
    for(int i=ssz-1;i>=0;--i){
        cur=pool+topsort[i];
        if(cur->flag)
            endpos[topsort[i]]++;
        //slink
        if(cur->fa!=nullptr)
            endpos[cur->fa-pool]+=endpos[topsort[i]];
    }
    //debug 
    // if(debug){
    //     cout<<"Debug endpos\n";
    //     for(int i=0;i<ssz;++i){
    //         cout<<i<<" "<<endpos[i]<<endl;
    //     }
    // }
}

int t,k;
ll dp[maxn<<1];
void solve(){
    sam_node *cur,*son;
    Topsort();
    getEndpos(t);
    for(int i=ssz-1;i>=0;--i){
        cur=pool+topsort[i];
        for(int j=0;j<CHAR;++j){
            if(cur->nxt[j]==nullptr) continue;
            dp[cur-pool]+=(endpos[cur->nxt[j]-pool]+dp[cur->nxt[j]-pool]);
        }
    }
    // if(debug){
    //     for(int i=0;i<ssz;++i){
    //         cout<<i<<" "<<dp[i]<<endl;
    //     }
    // }
    cur=root;
    while(k>0){
        int i;
        for(i=0;i<CHAR &&k>0;++i){
            son=cur->nxt[i];
            if(son==nullptr) continue;
            if(k<=dp[son-pool]+(endpos[son-pool])){
                //putchar('a'+i);
                printf("%c",i+'a');
                k-=endpos[son-pool];
                cur=son;
                break;
            }
            else{
                k-=dp[son-pool]+(endpos[son-pool]);//error2
            }
        }
        if(i==CHAR){
            puts("-1");
            break;
        }
    }
}

int main(){
    
    scanf(" %s %d %d",ori,&t,&k);
    build();
    solve();
    return 0;
}
/*
aabbabd
1 2
debug build output should be
10
0 a 1
0 b 5
0 d 9
1 a 2
1 b 8
2 b 3
3 b 4
4 a 6
5 a 6
5 b 4
5 d 9
6 b 7
7 d 9
8 b 4
8 d 9
*/