SPOJ SUBLEX

SUBLEX.cpp

#include <cstdio>
#include <cstring>
const int N = 90000 * 2 + 9;
char s[N];
int l[N],fa[N],ch[N][26],len,last,cnt,ec;
int f[N];
bool mark[N];
void query(int k)
{
    for (int p = 1; k; )
        for (int i = 0; i < 26; ++i)
            if (ch[p][i]) {
                if (f[ch[p][i]] >= k) {
                    putchar('a' + i);
                    p = ch[p][i];
                    --k;
                    break;
                }else k -= f[ch[p][i]];
            }
    puts("");
}
void add(int c)
{
    int p = last,np = ++cnt; last = np;
    l[np] = ++len;
    for (; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
    if (!p) fa[np] = 1;
    else {
        int q = ch[p][c];
        if (l[q] == l[p] + 1) fa[np] = q;
        else {
            int nq = ++cnt;
            memcpy(ch[nq],ch[q],sizeof ch[q]);
            fa[nq] = fa[q];
            l[nq] = l[p] + 1;
            fa[q] = fa[np] = nq;
            for (; ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
        }
    }
}
void dp()
{
    static int b[N],t[N];
    for (int i = 1; i <= cnt; ++i) ++b[l[i]];
    for (int i = 1; i <= len; ++i) b[i] += b[i - 1];
    for (int i = 1; i <= cnt; ++i) t[b[l[i]]--] = i;
    for (int i = cnt,v; i; --i) {
        f[v=t[i]] = 1;
        for (int j = 0; j < 26; ++j) {
            f[v] += f[ch[v][j]];//ec += (bool)(ch[i][j]);
        }
    }
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("SUBLEX.in","r",stdin);
    freopen("SUBLEX.out","w",stdout);
#endif
    last = cnt = 1;
    scanf("%s",s);
    for (char *c = s; *c; ++c) add(*c - 'a');
    dp();
    //printf("%d %d\n",3 * len,ec);
    int q = 0;
    scanf("%d",&q);
    while (q--) {
        int k;
        scanf("%d",&k);
        query(k);
    }
}