SPOJ Lexicographical Substring Search 求字典序第k大子串 后缀自动机

题目传送门

思路：按字典序，小的字符优先选取。对于一个字符，如果以这个字符开头的子串大于等于k个，那说明这个字符是应该选的，并且选完之后，可能还要继续选。如果以这个字符开头的子串小于k个，说明这个字符不能选，因为选完这个字符，后面无论怎么构造子串，都构造不出第k大的子串。

　　所以关键点就在于我们要统计每个字符开头的后面的子串数量，核心代码如下：

void topSort(){

    for(int i=;i<=tot;i++)c[len[i]]++;

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

    for(int i=tot;i>;i--)a[c[len[i]]--]=i;

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

        int p=a[i];

        r[p]++;

        for(int j=;j<;j++){

            if(ch[p][j]){

                r[p]+=r[ch[p][j]];

            }

        }

    }

}

为什么我们拓扑序从大到小更新是正确的呢？因为在自动机上，$ch[p][c]$的拓扑序必定是大于$p$的拓扑序的，因为$ch[p][c]$的$longest$比较大，所以这样更新不会遗留也不会重复。

还有一个要注意的点是，在查询的时候，如果以某一个字符开头的子串大于k，我们选取了这个字符，此时k也要减一，因为选到这个字符截止也是一种方案。

#include<bits/stdc++.h>

#define clr(a,b) memset(a,b,sizeof(a))

using namespace std;

typedef long long ll;

const int inf=0x3f3f3f3f;

const ll mod=1e9+;

const int maxn=;

char s[maxn];

int len[maxn<<],ch[maxn<<][],fa[maxn<<],tot=,root=,last=,siz,r[maxn<<],vis[maxn<<];

int a[maxn<<],c[maxn<<],ans[maxn<<];

ll dp[maxn<<];

void extend(int x){

    int now=++tot,pre=last;

    last=now,len[now]=len[pre]+;

    while( pre && !ch[pre][x]){

        ch[pre][x]=now;

        pre=fa[pre];

    }

    if(!pre)fa[now]=root;

    else{

        int q = ch[pre][x];

        if(len[q]==len[pre]+)fa[now]=q;

        else {

            int nows=++tot;

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

            len[nows]=len[pre]+;

            fa[nows]=fa[q];

            fa[q]=fa[now]=nows;

            while(pre&&ch[pre][x]==q){

                ch[pre][x]=nows;

                pre=fa[pre];

            }

        }

    }

}

void topSort(){

    for(int i=;i<=tot;i++)c[len[i]]++;

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

    for(int i=tot;i>;i--)a[c[len[i]]--]=i;

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

        int p=a[i];

        r[p]++;

        for(int j=;j<;j++){

            if(ch[p][j]){

                r[p]+=r[ch[p][j]];

            }

        }

    }

}

void query(int k){

    int now=root;

    while(k){

        for(int i=;i<;i++){

            if(ch[now][i]){

                int p=ch[now][i];

                if(r[p]>=k){

                    now=p;

                    putchar('a'+i);

                    k--;

                    break;

                }else{

                    k-=r[p];

                }

            }

        }

    }

    puts("");

}

int main(){

    scanf("%s",s);

    siz=strlen(s);

    for(int i=;i<siz;i++){

        int p=s[i]-'a';

        extend(p);

    }

    topSort();

    int n,k;

    cin>>n;

    while(n--){

        cin>>k;

        query(k);

    }

}