rt

感觉自己跟 SPOJ 有仇

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>

#define N 200001
#define LL long long

using namespace std;
string s;

int tot=1,np=1,ch[N][26],fail[N],len[N];

void ins(int c) {
    int p=np; len[np=++tot]=len[p]+1;
    while (p and !ch[p][c]) ch[p][c]=np,p=fail[p];
    if (!p) fail[np]=1;
    else {
        int q=ch[p][c];
        if (len[q]==len[p]+1) fail[np]=q;
        else {
            int nq=++tot;
            len[nq]=len[p]+1,fail[nq]=fail[q];
            fail[np]=fail[q]=nq;
            memcpy(ch[nq],ch[q],sizeof ch[q]);
            while (p and ch[p][c]==q) ch[p][c]=nq,p=fail[p];
        }
    }
}

LL siz[N];

void dfs1(int u) {
    if (siz[u]) return;
    siz[u]=(u!=1);
    for (int i=0;i<26;i++) {
        if (!ch[u][i]) continue;
        dfs1(ch[u][i]);
        siz[u]+=siz[ch[u][i]];
    }
}

string ans;

void find(int u,int k) {
    if (k==1) return;
    k-=(u!=1);
    for (int i=0;i<26;i++) {
        if (!ch[u][i]) continue;
        if (siz[ch[u][i]]>=k) return ans.push_back('a'+i),find(ch[u][i],k);
        else k-=siz[ch[u][i]];
    }
}

signed main() {
    cin>>s;
    for (char c:s) ins(c-'a');
    dfs1(1);
    int q; scanf("%d",&q);
    for (int i=1,k;i<=q;i++) {
        scanf("%d",&k);
        if (siz[1]<k) {
            // printf("\n");
            continue;
        }
        ans.clear(); find(1,k);
        cout<<ans<<'\n';
    }
    return 0;
}