[SPOJ SUBLEX]SUBLEX - Lexicographical Substring Search

這題目不好找，附上題目連結

這裡提供了另外一個做法，選個喜歡的去實現吧～

這題問你$500$次去重後字典序第$k$小的子字串

可以發現，後綴自動機已經幫你將子字串們自動去重了！
而且更棒的是，把後綴自動機當作樹遍歷一次，每一個子字串都會被遇到恰好一次！

當然，這題不能直接遍歷找第$k$個節點
有一個很棒的優化方法就是，當我們發現一棵子樹，它的大小太小以致遍歷完這棵子樹後計數器仍$\leq k$，那麼我們可以直接將計數器的值加上這棵子樹的大小 (或將$k$減掉這棵子樹的大小)，直接考慮下一棵子樹

因此，我們只需要先預處理後綴自動機的每個節點代表的子樹大小即可

時間複雜度：$O(N)$ (不過常數非常大，就算各種優化也不見起色，時間是這個寫法的$6$倍Orz)

code:

#include<cstdio>
#include<cassert>
#include<map>
using namespace std;
typedef long long LL;
struct Node
{
    Node *parent;
    map<char,Node*>trans;
    int max_len;
    LL sz;
    bool Contains(const char c){return trans.find(c)!=trans.end();}
}*ROOT,*LAST,BUFFER[180001],*NEW;
Node *NewNode(const int _max_len)
{
    NEW->parent=NULL;
    NEW->max_len=_max_len;
    NEW->sz=-1LL;
    NEW->trans.clear();
    return NEW++;
}
void Expand(const char c)
{
    Node *cur=LAST;LAST=NewNode((LAST->max_len)+1);
    for(;cur&&!cur->Contains(c);cur=cur->parent)cur->trans[c]=LAST;
    if(!cur)LAST->parent=ROOT;
    else
    {
        Node *q=cur->trans[c];
        if((cur->max_len)+1==(q->max_len))LAST->parent=q;
        else
        {
            Node *new_q=NewNode((cur->max_len)+1);
            new_q->trans=q->trans;
            new_q->parent=q->parent;
            q->parent=new_q;
            LAST->parent=new_q;
            for(;cur&&cur->trans[c]==q;cur=cur->parent)cur->trans[c]=new_q;
        }
    }
}
LL GetSz(Node *o)
{
    if(o->sz!=-1LL)return o->sz;
    o->sz=1LL;
    for(const auto &it:o->trans)o->sz+=GetSz(it.second);
    return o->sz;
}
void PrintAns(Node *o,const LL &k)
{
    if(k==1LL)return;
    LL sz=1LL;
    for(const auto &it:o->trans)
    {
        if(sz+(it.second->sz)>=k)
        {
            putchar(it.first);
            PrintAns(it.second,k-sz);
            return;
        }
        sz+=it.second->sz;
    }
    assert(0);
}
int main()
{
//    freopen("in.txt","r",stdin);
    NEW=BUFFER;
    int c=getchar();
    while(c<'a'||c>'z')c=getchar();
    ROOT=LAST=NewNode(0);
    for(;c>='a'&&c<='z';c=getchar())Expand(c);
    GetSz(ROOT);
    int querycount;scanf("%d",&querycount);
    for(LL k;querycount--;)
    {
        scanf("%lld",&k);
        PrintAns(ROOT,k+1LL);puts("");
    }
    return 0;
}