Table of Contents
Ashton and String – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Ashton and String HackerRank Solution
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
typedef long long LL;
using namespace std;
const int MAXLEN = (int)1e5 + 5;
char s[MAXLEN];
int SA[MAXLEN], cnt[MAXLEN], ary1[MAXLEN], ary2[MAXLEN];
int *Rank, *Height;
inline bool cmp(int *r, int a, int b, int l) {
return r[a] == r[b] && r[a + l] == r[b + l];
}
void make_suffix_array(int MSIZE, int len) {
int p, *x, *y, *tmp, i, j, k;
x = ary1; y = ary2;
memset(cnt, 0, sizeof(int) * MSIZE);
for (i = 0; i < len; i++) cnt[x[i] = s[i]]++;
for (i = 1; i < MSIZE; i++) cnt[i] += cnt[i - 1];
for (i = len - 1; i >= 0; i--) SA[--cnt[x[i]]] = i;
for (j = p = 1; p < len; j <<= 1, MSIZE = p) {
for (p = 0, i = len - j; i < len; i++) y[p++] = i;
for (i = 0; i < len; i++) {
if (SA[i] >= j) y[p++] = SA[i] - j;
}
memset(cnt, 0, sizeof(int) * MSIZE);
for (i = 0; i < len; i++) cnt[x[y[i]]]++;
for (i = 1; i < MSIZE; i++) cnt[i] += cnt[i - 1];
for (i = len - 1; i >= 0; i--) SA[--cnt[x[y[i]]]] = y[i];
tmp = x; x = y; y = tmp;
x[SA[0]] = 0;
for (i = p = 1; i < len; i++) {
x[SA[i]] = cmp(y, SA[i - 1], SA[i], j) ? p - 1 : p++;
}
}
Rank = x;
Height = y;
for (i = k = 0; i < len - 1; i++) {
if (k > 0) k--;
j = SA[Rank[i] - 1];
while (s[i + k] == s[j + k]) k++;
Height[Rank[i]] = k;
}
}
LL get(LL x,LL y){
return (x+y)*(y-x+1)/2;
}
int main(){
CASET{
RS(s);
int n=LEN(s);
LL K;
cin>>K;
make_suffix_array(128,n+1);
int now=0;
REPP(i,1,n+1){
now=Height[i];
if(K<=get(now+1,n-SA[i])){
LL ll=now+1,rr=n-SA[i];
while(ll<rr){
LL mm=(ll+rr)>>1;
if(get(now+1,mm)<K)ll=mm+1;
else rr=mm;
}
K-=get(now+1,ll-1);
printf("%c\n",s[SA[i]+K-1]);
break;
}
else K-=get(now+1,n-SA[i]);
}
}
return 0;
}
Java Ashton and String HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class Solution {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
static void solve()
{
for(int T = ni();T >= 1;T--){
char[] s = ns().toCharArray();
long K = nl();
int[] sa = sa(s);
int[] lcp = buildLCP0(s, sa);
int n = s.length;
out:
for(int i = 0;i < lcp.length;i++){
// long num = (n-sa[i]-lcp[i]);
long len = (long)(n-sa[i])*(n-sa[i]+1)/2 - (long)lcp[i]*(lcp[i]+1)/2;
if(K <= len){
for(int j = lcp[i]+1;j <= n-sa[i];j++){
long llen = j;
if(K <= llen){
out.println(s[(int)(sa[i]+K-1)]);
break out;
}else{
K -= llen;
}
}
break;
}else{
K -= len;
}
}
}
}
private static interface BaseArray {
public int get(int i);
public void set(int i, int val);
public int update(int i, int val);
}
private static class CharArray implements BaseArray {
private char[] m_A = null;
private int m_pos = 0;
CharArray(char[] A, int pos) {
m_A = A;
m_pos = pos;
}
public int get(int i) {
return m_A[m_pos + i] & 0xffff;
}
public void set(int i, int val) {
m_A[m_pos + i] = (char) (val & 0xffff);
}
public int update(int i, int val) {
return m_A[m_pos + i] += val & 0xffff;
}
}
private static class IntArray implements BaseArray {
private int[] m_A = null;
private int m_pos = 0;
IntArray(int[] A, int pos) {
m_A = A;
m_pos = pos;
}
public int get(int i) {
return m_A[m_pos + i];
}
public void set(int i, int val) {
m_A[m_pos + i] = val;
}
public int update(int i, int val) {
return m_A[m_pos + i] += val;
}
}
/* find the start or end of each bucket */
private static void getCounts(BaseArray T, BaseArray C, int n, int k) {
int i;
for(i = 0;i < k;++i){
C.set(i, 0);
}
for(i = 0;i < n;++i){
C.update(T.get(i), 1);
}
}
private static void getBuckets(BaseArray C, BaseArray B, int k, boolean end) {
int i, sum = 0;
if(end != false){
for(i = 0;i < k;++i){
sum += C.get(i);
B.set(i, sum);
}
}else{
for(i = 0;i < k;++i){
sum += C.get(i);
B.set(i, sum - C.get(i));
}
}
}
/* sort all type LMS suffixes */
private static void LMSsort(BaseArray T, int[] SA, BaseArray C,
BaseArray B, int n, int k) {
int b, i, j;
int c0, c1;
/* compute SAl */
if(C == B){
getCounts(T, C, n, k);
}
getBuckets(C, B, k, false); /* find starts of buckets */
j = n - 1;
b = B.get(c1 = T.get(j));
--j;
SA[b++] = (T.get(j) < c1) ? ~j : j;
for(i = 0;i < n;++i){
if(0 < (j = SA[i])){
if((c0 = T.get(j)) != c1){
B.set(c1, b);
b = B.get(c1 = c0);
}
--j;
SA[b++] = (T.get(j) < c1) ? ~j : j;
SA[i] = 0;
}else if(j < 0){
SA[i] = ~j;
}
}
/* compute SAs */
if(C == B){
getCounts(T, C, n, k);
}
getBuckets(C, B, k, true); /* find ends of buckets */
for(i = n - 1, b = B.get(c1 = 0);0 <= i;--i){
if(0 < (j = SA[i])){
if((c0 = T.get(j)) != c1){
B.set(c1, b);
b = B.get(c1 = c0);
}
--j;
SA[--b] = (T.get(j) > c1) ? ~(j + 1) : j;
SA[i] = 0;
}
}
}
private static int LMSpostproc(BaseArray T, int[] SA, int n, int m) {
int i, j, p, q, plen, qlen, name;
int c0, c1;
boolean diff;
/*
* compact all the sorted substrings into the first m items of SA 2*m
* must be not larger than n (proveable)
*/
for(i = 0;(p = SA[i]) < 0;++i){
SA[i] = ~p;
}
if(i < m){
for(j = i, ++i;;++i){
if((p = SA[i]) < 0){
SA[j++] = ~p;
SA[i] = 0;
if(j == m){
break;
}
}
}
}
/* store the length of all substrings */
i = n - 1;
j = n - 1;
c0 = T.get(n - 1);
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
for(;0 <= i;){
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) <= c1));
if(0 <= i){
SA[m + ((i + 1) >> 1)] = j - i;
j = i + 1;
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
}
}
/* find the lexicographic names of all substrings */
for(i = 0, name = 0, q = n, qlen = 0;i < m;++i){
p = SA[i];
plen = SA[m + (p >> 1)];
diff = true;
if((plen == qlen) && ((q + plen) < n)){
for(j = 0;(j < plen) && (T.get(p + j) == T.get(q + j));++j){
}
if(j == plen){
diff = false;
}
}
if(diff != false){
++name;
q = p;
qlen = plen;
}
SA[m + (p >> 1)] = name;
}
return name;
}
/* compute SA and BWT */
private static void induceSA(BaseArray T, int[] SA, BaseArray C,
BaseArray B, int n, int k) {
int b, i, j;
int c0, c1;
/* compute SAl */
if(C == B){
getCounts(T, C, n, k);
}
getBuckets(C, B, k, false); /* find starts of buckets */
j = n - 1;
b = B.get(c1 = T.get(j));
SA[b++] = ((0 < j) && (T.get(j - 1) < c1)) ? ~j : j;
for(i = 0;i < n;++i){
j = SA[i];
SA[i] = ~j;
if(0 < j){
if((c0 = T.get(--j)) != c1){
B.set(c1, b);
b = B.get(c1 = c0);
}
SA[b++] = ((0 < j) && (T.get(j - 1) < c1)) ? ~j : j;
}
}
/* compute SAs */
if(C == B){
getCounts(T, C, n, k);
}
getBuckets(C, B, k, true); /* find ends of buckets */
for(i = n - 1, b = B.get(c1 = 0);0 <= i;--i){
if(0 < (j = SA[i])){
if((c0 = T.get(--j)) != c1){
B.set(c1, b);
b = B.get(c1 = c0);
}
SA[--b] = ((j == 0) || (T.get(j - 1) > c1)) ? ~j : j;
}else{
SA[i] = ~j;
}
}
}
/*
* find the suffix array SA of T[0..n-1] in {0..k-1}^n use a working space
* (excluding T and SA) of at most 2n+O(1) for a constant alphabet
*/
private static void SA_IS(BaseArray T, int[] SA, int fs, int n, int k) {
BaseArray C, B, RA;
int i, j, b, m, p, q, name, newfs;
int c0, c1;
int flags = 0;
if(k <= 256){
C = new IntArray(new int[k], 0);
if(k <= fs){
B = new IntArray(SA, n + fs - k);
flags = 1;
}else{
B = new IntArray(new int[k], 0);
flags = 3;
}
}else if(k <= fs){
C = new IntArray(SA, n + fs - k);
if(k <= (fs - k)){
B = new IntArray(SA, n + fs - k * 2);
flags = 0;
}else if(k <= 1024){
B = new IntArray(new int[k], 0);
flags = 2;
}else{
B = C;
flags = 8;
}
}else{
C = B = new IntArray(new int[k], 0);
flags = 4 | 8;
}
/*
* stage 1: reduce the problem by at least 1/2 sort all the
* LMS-substrings
*/
getCounts(T, C, n, k);
getBuckets(C, B, k, true); /* find ends of buckets */
for(i = 0;i < n;++i){
SA[i] = 0;
}
b = -1;
i = n - 1;
j = n;
m = 0;
c0 = T.get(n - 1);
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
for(;0 <= i;){
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) <= c1));
if(0 <= i){
if(0 <= b){
SA[b] = j;
}
b = B.update(c1, -1);
j = i;
++m;
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
}
}
if(1 < m){
LMSsort(T, SA, C, B, n, k);
name = LMSpostproc(T, SA, n, m);
}else if(m == 1){
SA[b] = j + 1;
name = 1;
}else{
name = 0;
}
/*
* stage 2: solve the reduced problem recurse if names are not yet
* unique
*/
if(name < m){
if((flags & 4) != 0){
C = null;
B = null;
}
if((flags & 2) != 0){
B = null;
}
newfs = (n + fs) - (m * 2);
if((flags & (1 | 4 | 8)) == 0){
if((k + name) <= newfs){
newfs -= k;
}else{
flags |= 8;
}
}
for(i = m + (n >> 1) - 1, j = m * 2 + newfs - 1;m <= i;--i){
if(SA[i] != 0){
SA[j--] = SA[i] - 1;
}
}
RA = new IntArray(SA, m + newfs);
SA_IS(RA, SA, newfs, m, name);
RA = null;
i = n - 1;
j = m * 2 - 1;
c0 = T.get(n - 1);
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
for(;0 <= i;){
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) <= c1));
if(0 <= i){
SA[j--] = i + 1;
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
}
}
for(i = 0;i < m;++i){
SA[i] = SA[m + SA[i]];
}
if((flags & 4) != 0){
C = B = new IntArray(new int[k], 0);
}
if((flags & 2) != 0){
B = new IntArray(new int[k], 0);
}
}
/* stage 3: induce the result for the original problem */
if((flags & 8) != 0){
getCounts(T, C, n, k);
}
/* put all left-most S characters into their buckets */
if(1 < m){
getBuckets(C, B, k, true); /* find ends of buckets */
i = m - 1;
j = n;
p = SA[m - 1];
c1 = T.get(p);
do{
q = B.get(c0 = c1);
while (q < j){
SA[--j] = 0;
}
do{
SA[--j] = p;
if(--i < 0){
break;
}
p = SA[i];
}while ((c1 = T.get(p)) == c0);
}while (0 <= i);
while (0 < j){
SA[--j] = 0;
}
}
induceSA(T, SA, C, B, n, k);
C = null;
B = null;
}
/* char */
public static void suffixsort(char[] T, int[] SA, int n) {
if((T == null) || (SA == null) || (T.length < n) || (SA.length < n)){
return;
}
if(n <= 1){
if(n == 1){
SA[0] = 0;
}
return;
}
SA_IS(new CharArray(T, 0), SA, 0, n, 128);
}
public static int[] sa(char[] T)
{
int n = T.length;
int[] sa = new int[n];
suffixsort(T, sa, n);
return sa;
}
public static int[] buildLCP0(char[] str, int[] sa)
{
int n = str.length;
int h = 0;
int[] lcp = new int[n];
int[] b = new int[n];
for(int i = 0;i < n;i++)b[sa[i]] = i;
for(int i = 0;i < n;i++){
if(b[i] > 0){
for(int j = sa[b[i]-1]; j+h<n && i+h<n && str[j+h] == str[i+h]; h++);
lcp[b[i]] = h;
}else{
lcp[b[i]] = 0;
}
if(h > 0)h--;
}
return lcp;
}
public static void main(String[] args) throws Exception
{
// int n = 100000, m = 99999;
// Random gen = new Random();
// StringBuilder sb = new StringBuilder();
// sb.append(1 + " ");
// for(int i = 0;i < n;i++){
// sb.append((char)(gen.nextInt(26)+'a'));
// }
// sb.append(" " + gen.nextInt(10000000)+1 + " ");
// INPUT = sb.toString();
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}
private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}
private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;
private static int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private static double nd() { return Double.parseDouble(ns()); }
private static char nc() { return (char)skip(); }
private static String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private static char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
Python 3 Ashton and String HackerRank Solution
import sys
def rendez(s,slen,l,l_first,l_last, diffstart):
#print((s,slen,l,l_first,l_last, diffstart))
#print((l_first,l_last, diffstart))
if l_first>=l_last:
return
diffstart1=diffstart
while True:
sm_ord_min=ord('z')+1
sm_ord_max=ord('a')-2
for l_i in range(l_first, l_last+1):
sm_ord = ord(s[l[l_i]+diffstart1]) if l[l_i]+diffstart1<slen else ord('a')-1
if sm_ord<sm_ord_min:
sm_ord_min=sm_ord
if sm_ord>sm_ord_max:
sm_ord_max=sm_ord
if sm_ord_min==sm_ord_max:
diffstart1+=1
else:
break
sm = chr(int((sm_ord_min+sm_ord_max+1)/2))
i1=l_first
i2=l_last
try:
while i1<i2:
if l[i1]+diffstart1==slen or s[l[i1]+diffstart1] < sm:
i1+=1
elif l[i2]+diffstart1<slen and s[l[i2]+diffstart1] >= sm:
i2-=1
else:
ll=l[i1]
l[i1]=l[i2]
l[i2]=ll
i1+=1
#i2-=1
except:
print((slen,l_first,l_last, i1,i2, l[i1], l[i2],diffstart, sm))
return
rendez(s,slen,l,l_first,i1-1,diffstart1)
rendez(s,slen,l,i1,l_last,diffstart1)
def testcase(s,k):
slenarray=[0]*(len(s)+1)
for i in range(1,len(s)+1):
slenarray[i]=slenarray[i-1]+i
#t0=time.time()
l = list(range(len(s)))
rendez(s,len(s),l,0,len(l)-1,0)
#for i in range(min(30,len(s))):
# print((i,l[i],s[l[i]:l[i]+20]))
#for i in range(1,len(s)):
# s0=s[l[i-1]:l[i-1]+20]
# s1=s[l[i]:l[i]+20]
# if not s0<s1:
# print(i)
# print(s0)
# print(s1)
# break
#l.sort(key=lambda d:s[d:])
#print(time.time()-t0)
#for i in range(len(s)):
# print(s[l[i]:])
'''
t0=time.time()
l = list(range(len(s)))
chg = True
im = len(s)-1
while chg:
#print(l)
for i in range(len(s)):
#print(s[l[i]:])
pass
#print()
chg=False
for i in range(im):
#print("compare: "+str((s[l[i]:],s[l[i+1]:])))
if s[l[i]:]>s[l[i+1]:]:
#print(" ->chg")
l1 = l[i+1]
l[i+1]=l[i]
l[i]=l1
chg=True
im = im -1
#data=[s,len(s),k]
print(time.time()-t0)
'''
#t0=time.time()
for i in range(len(s)):
s0=s[l[i-1]:] if i>0 else ""
s1=s[l[i]:]
diffstart=0
while diffstart<len(s0) and diffstart<len(s1) and s0[diffstart]==s1[diffstart]:
diffstart = diffstart+1
slen=slenarray[len(s1)]-slenarray[diffstart]
#print(str((s0,s1,diffstart,slen,k)))
if k<=slen:
d=diffstart+1
while k>0:
if k<=d:
print(s1[k-1])
k=0
break
else:
k=k-d
d=d+1
else:
k=k-slen
if k==0:
break
#print(time.time()-t0)
#print()
testcount = int(sys.stdin.readline())
for i in range(testcount):
s=sys.stdin.readline()[:-1]
k=int(sys.stdin.readline())
#print("testcase "+str(i)+" :")
testcase(s,k)
Python 2 Ashton and String HackerRank Solution
# ashton
def substring_from_index(string, idx):
for i in range(idx + 1, len(string) + 1):
yield string[:i]
return
def substring_from_list(suffixes, k):
suffixes.sort()
substrs = ""
last_suffix = ""
for suffix in suffixes:
# first, if this is a repeat, skip it
if suffix == last_suffix:
continue
idx = 0
# second, if this is the first value, process the entire thing
if last_suffix != "":
idx = 1 # first letter will always be the same
while idx < len(suffix) and idx < len(last_suffix) and last_suffix[idx] == suffix[idx]:
idx = idx + 1
for substr in substring_from_index(suffix, idx):
if len(substr) < k:
k = k - len(substr)
else:
return (substr[k], k)
last_suffix = suffix
return (None, k)
ALPHABET = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o',
'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
def make_suffix_dict(word):
suffix_indexes = dict()
for i, ch in enumerate(word):
if ch not in suffix_indexes:
suffix_indexes[ch] = [i]
else:
suffix_indexes[ch].append(i)
return suffix_indexes
def get_suffixes(word, suffix_indexes):
suffixes = [word[idx:] for idx in suffix_indexes]
return suffixes
def find_kth_char(word, k):
suffix_indexes = make_suffix_dict(word)
for letter in ALPHABET:
if letter in suffix_indexes:
suffixes = get_suffixes(word, suffix_indexes[letter])
(ch, k) = substring_from_list(suffixes, k)
if ch:
return ch
test_cases = int(input())
for i in range(0, test_cases):
line = raw_input()
k = int(raw_input()) - 1
print find_kth_char(line, k)
C Ashton and String HackerRank Solution
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define MAX 100010
#define clr(ar) memset(ar, 0, sizeof(ar))
#define read() freopen("lol.txt", "r", stdin)
char str[MAX];
long long sum[MAX];
int s0[(MAX / 3) + 10], sa0[(MAX / 3) + 10];
int n, ar[MAX], sa[MAX], lcp[MAX], bucket[MAX], mem[MAX << 2];
void radixsort(int* source, int* dest, int* val, int n, int lim){
int i, s = 0, x;
memset(bucket, 0, lim << 2);
for (i = 0; i < n; i++) bucket[val[source[i]]]++;
for (i = 0; i < lim; i++){
x = bucket[i];
bucket[i] = s, s += x;
}
for (i = 0; i < n; i++) dest[bucket[val[source[i]]]++] = source[i];
}
void DC3(int* ar, int* sa, int n, int lim, int ptr){
int *s12, *sa12;
int allc = (n / 3) << 1, n0 = (n + 2) / 3;
int i, j, k, l, c, d, p, t, m, r, counter;
s12 = &mem[ptr], ptr += (allc + 5), sa12 = &mem[ptr], ptr += (allc + 5);
c = 0, m = 0, r = n + ((n % 3) == 1);
for (i = 0; i < r; i++, m++){
if (m == 3) m = 0;
if (m) s12[c++] = i;
}
s12[c] = sa12[c] = s12[c + 1] = sa12[c + 1] = s12[c + 2] = sa12[c + 2] = 0;
radixsort(s12, sa12, ar + 2, c, lim + 1);
radixsort(sa12, s12, ar + 1, c, lim + 1);
radixsort(s12, sa12, ar, c, lim + 1);
counter = 0, j = -1;
for (i = 0; i < c; i++){
if ((ar[sa12[i]] != j) || (ar[sa12[i] + 1] != k) || (ar[sa12[i] + 2] != l)){
counter++;
j = ar[sa12[i]], k = ar[sa12[i] + 1], l = ar[sa12[i] + 2];
}
if((sa12[i] % 3) == 1) s12[sa12[i] / 3] = counter;
else s12[(sa12[i] / 3) + n0] = counter;
}
if (counter == c){
for(i = 0; i < c; i++) sa12[s12[i] - 1] = i;
}
else{
DC3(s12, sa12, c, counter, ptr);
for (i = 0; i < c; i++) s12[sa12[i]] = i + 1;
}
for (i = 0, d = 0; i < c; i++){
if (sa12[i] < n0) s0[d++] = (sa12[i] * 3);
}
radixsort(s0, sa0, ar, d, lim + 1);
for (k = 0, l = ((n % 3) == 1), r = 0; r < n; r++){
j = sa0[k];
i = ((sa12[l] < n0) ? (sa12[l] * 3) + 1 : ((sa12[l] - n0) * 3) + 2);
if (l == c) sa[r] = sa0[k++];
else if (k == d) sa[r] = i, l++;
else{
if (sa12[l] < n0){
if ((ar[i] < ar[j]) || (ar[i] == ar[j] && s12[sa12[l] + n0] <= s12[j / 3])) sa[r] = i, l++;
else sa[r] = j, k++;
}
else{
if ((ar[i] < ar[j]) || (ar[i] == ar[j] && ar[i + 1] < ar[j + 1]) || (ar[i] == ar[j] && ar[i + 1] == ar[j + 1] && s12[sa12[l] - n0 + 1] <= s12[(j /3) + n0]) ) sa[r] = i, l++;
else sa[r] = j, k++;
}
}
}
}
void LcpArray(){
int i, j, k;
for (i = 0; i < n; i++) ar[sa[i]] = i;
for (k = 0, i = 0; i < n; i++, k?k--:0){
if (ar[i] == (n - 1)) k = 0;
else{
j = sa[ar[i] + 1];
while(((i + k) < n) && ((j + k) < n) && (str[i + k] == str[j + k])) k++;
}
lcp[ar[i]] = k;
}
}
void Generate(){
int i, j, lim = 0;
for (i = 0; i < n; i++){
ar[i] = str[i];
if (ar[i] > lim) lim = ar[i];
}
ar[n] = ar[n + 1] = ar[n + 2] = 0;
DC3(ar, sa, n, lim, 0);
}
long long F(long long a, long long n){
long long res = (((a << 1LL) + (n - 1)) * n) >> 1LL;
return res;
}
int main(){
long long k, x, y, total;
int t, i, j, c, d, len, pos;
sum[0] = 0;
for (i = 1; i < MAX; i++){
x = i;
sum[i] = sum[i - 1] + ((x * (x + 1)) >> 1LL);
}
scanf("%d", &t);
while (t--){
scanf("%s", str);
scanf("%lld", &k);
n = strlen(str);
Generate();
LcpArray();
for (i = 0; i < n; i++){
c = 0, pos = sa[i];
if (i) c = lcp[i - 1];
total = F(c + 1, n - (pos + c));
if (k > total) k -= total;
else{
len = c + 1;
for (j = pos + c; j < n; j++){
if (k > len) k -= len;
else{
printf("%c\n", str[pos + k - 1]);
break;
}
len++;
}
break;
}
}
}
return 0;
}
Comments 1