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

题目传送门

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

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

void topSort(){
    for(int i=1;i<=tot;i++)c[len[i]]++;
    for(int i=1;i<=tot;i++)c[i]+=c[i-1];
    for(int i=tot;i>0;i--)a[c[len[i]]--]=i;
    for(int i=tot;i>0;i--){
        int p=a[i];
        r[p]++;
        for(int j=0;j<26;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+7;
const int maxn=200010;
char s[maxn];
int len[maxn<<1],ch[maxn<<1][27],fa[maxn<<1],tot=1,root=1,last=1,siz,r[maxn<<1],vis[maxn<<1];
int a[maxn<<1],c[maxn<<1],ans[maxn<<1];
ll dp[maxn<<1];
void extend(int x){
    int now=++tot,pre=last;
    last=now,len[now]=len[pre]+1;
    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]+1)fa[now]=q;
        else {
            int nows=++tot;
            memcpy(ch[nows],ch[q],sizeof(ch[q]));
            len[nows]=len[pre]+1;
            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=1;i<=tot;i++)c[len[i]]++;
    for(int i=1;i<=tot;i++)c[i]+=c[i-1];
    for(int i=tot;i>0;i--)a[c[len[i]]--]=i;
    for(int i=tot;i>0;i--){
        int p=a[i];
        r[p]++;
        for(int j=0;j<26;j++){
            if(ch[p][j]){
                r[p]+=r[ch[p][j]];
            }
        }
    }
}
void query(int k){
    int now=root;
    while(k){
        for(int i=0;i<26;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=0;i<siz;i++){
        int p=s[i]-'a';
        extend(p);
    }
    topSort();
    int n,k;
    cin>>n;
    while(n--){
        cin>>k;
        query(k);
    }


}