ashton.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

#define MAX_STRING 100001

static char s[MAX_STRING] ;
static unsigned sl ;

struct rtree {
    unsigned b, e ; // prefix beginning / end
    struct rtree *more[26] ;
} ;

static void rt_add(struct rtree *t, unsigned b) {
    unsigned i, cl = (sl - b > t->e - t->b) ? (t->e - t->b) : (sl - b) ;

    for (i = 0; i < cl && s[t->b + i] == s[b + i]; i ++) ;

    if (t->b + i < t->e) {
        struct rtree *t2 = calloc(sizeof(*t2), 1) ;
        assert(t2) ;
        *t2 = *t ;
        t2->b = t->b + i + 1 ;
        t->e = t->b + i ;
        memset(&(t->more), 0, sizeof(t->more)) ;
        t->more[s[t->b + i] - 'a'] = t2 ;
    }

    assert(sl - b >= t->e - t->b) ;
    if (sl - b == t->e - t->b)
        return ;

    int ci = s[b + i] - 'a' ;

    if (t->more[ci]) return rt_add(t->more[ci], b + i + 1) ;

    struct rtree *t2 = calloc(sizeof(*t2), 1) ;
    assert(t2) ;
    t2->b = b + i + 1 ;
    t2->e = sl ;
    t->more[ci] = t2 ;
}

static struct rtree *rt_init(void) {
    struct rtree *t = calloc(sizeof(*t), 1) ;
    assert(t) ;
    t->b = 0 ;
    t->e = sl ;

    for (unsigned i = 1; i < sl; i ++) rt_add(t, i) ;
    return t ;
}

static void rt_destroy(struct rtree *t) {
    for (int c = 0; c <= 'z' - 'a'; c ++)
        if (t->more[c]) rt_destroy(t->more[c]) ;
    free(t) ;
}

static int rt_ref(struct rtree *t, int i, int pad) {
    unsigned n = t->e - t->b ;
    unsigned l = pad + n * pad + n * (n + 1) / 2 ;

    if (l > i) {
        for (int j = 0; j <= n; j ++) {
            i -= pad ;
            if (i < 0) return i ;

            if (i < j) {
                printf("%c\n", s[t->b + i]) ;
                return 0 ;
            }
            i -= j ;
        }
        abort() ;
    } else
        i -= l ;

    for (int c = 0; c <= 'z' - 'a'; c ++)
        if (t->more[c]) {
            i = rt_ref(t->more[c], i, pad + n + 1) ;

            if (!i) return i ;
            if (i > 0) continue ;

            if (i == -1) {
                printf("%c\n", c + 'a') ;
                return 0 ;
            }

            i = t->e - t->b + i + 1 ;
            if (i >= 0) {
                printf("%c\n", s[t->b + i]) ;
                return 0 ;
            }
            break ;
        }

    return i ;
}

static int read_int(void) {
    char b[32] ;
    assert(fgets(b, sizeof(b), stdin)) ;
    return atoi(b) ;
}

int main(int ac, const char *av[]) {
    int t = read_int() ;

    while (t --) {
        assert(fgets(s, sizeof(s), stdin)) ;
        sl = strlen(s) - 1 ;
        s[sl] = 0 ;

        int n = read_int() - 1 ;
        struct rtree *t = rt_init() ;
        rt_ref(t, n, 0) ;
        rt_destroy(t) ;
    }
    return 0 ;
}