Shared code

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef pair<int, int> pii;
#define endl "\n"
#define all(v) v.begin(),v.end() 

#define trace1(x)       if(dm) cout<<(#x)<<" "<<(x)<<endl
#define trace2(x,y)     if(dm) cout<<(#x)<<" "<<(x)<<", "<<(#y)<<" "<<(y)<<endl
#define trace3(x,y,z)   if(dm) cout<<(#x)<<" "<<(x)<<", "<<(#y)<<" "<<(y)<<", "<<(#z)<<" "<<(z)<<endl
int dm = 0;
void fastio(){ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
void fileio() {
	#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
	#endif
}



vector<int> suffix_array(const string& str){
    // return sorted position of each suffix, 'pos'
    // pos[k] = i => kth smallest suffix is suffix[i...n-1]

    string s = str + '$'; // '$' is smaller than all character;

    int n = s.size();
    vector<int> clss(n, 0);
    vector<int> pos(n,0);
    // clss[i] = k => suffix s[i...n-1] is kth smallest suffix in sorted order.
    // its like sort of inverse of pos[] array, and both arrays can be computed from each other

    // ----------  Step 1 
    // build initial clss for only first character
    vector<int> cnt(126,0);
    vector<int> cntsum(127,0);
    vector<vector<int>> idx_with_clss(n);
    vector<int> newclss(n,-1);
    for(int i=0; i<n; i++){
        cnt[s[i]]++;
    }
    for(int i=1; i<=126; i++){
        cntsum[i] = cntsum[i-1] + cnt[i-1];
    }
    for(int i=0; i<n; i++){
        clss[i] = cntsum[ s[i] ] ;
        pos[ cntsum[s[i]] + (cnt[s[i]]-1) ] = i;
        cnt[s[i]]--;
    }

    // ----------- Step 2
    int prevlen = 1;
    int len = 2;
    while(len<=n){
        // we know the order for string of some prevlen >= len/2
        // we want to order the shifts for length len [0...len-1]
        // first order the shifts according to rank of their [prevlen...len-1]   
        // then we order then acc to rank of [0..prevlen-1]

        // pos[k+x] = i, pos[k] = j
        // implies i appears after j
        // <=> for shift i, [prevlen...len-1] is having clss bigger than for shift j,[prevlen...len-1]
        // order shift 'i' according to clss[(i+prevlen)%n]
        // then order shift 'i' according to clss[i] 

        // Step A : order acc to clss[ (i+prevlen) % n]

        for(int i=0; i<n; i++){
            idx_with_clss[i].clear();
        }
        for(int i=0; i<n;i++){
            idx_with_clss[ clss[(i+prevlen)%n] ].push_back(i);
        }
        int k=0;
        for(int i=0; i<n; i++){
            for(int idx : idx_with_clss[i]){
                pos[k++] = idx;
            }
        }

        // Step B : order acc to clss[i]
        for(int i=0; i<n; i++){
            idx_with_clss[i].clear();
        }

        for(int order=0; order<n;order++){
            idx_with_clss[ clss[pos[order]] ].push_back(pos[order]);
        }
        k=0;
        for(int i=0; i<n; i++){
            for(int idx : idx_with_clss[i]){
                
                pos[k++] = idx;
                // can put the next loop here 
            }
        }

        assert(k==n);


        // Step C : Find clss array using pos
        newclss[pos[0]] = 0;
        int curclss = 0;
        for(int ord=1; ord<n; ord++){
            // shift with pos[ord-1] <= shift with pos[ord] till length 'len'
            // if greater then higher class otherwise same
            int i=pos[ord-1];
            int j=pos[ord];

            if(clss[j]>clss[i] || 
            (clss[i]==clss[j] && (clss[(j+prevlen)%n]>clss[(i+prevlen)%n]) ) )
            {
                curclss++;
            }

            newclss[j] = curclss;
        }
        
        for(int i=0; i<n; i++) clss[i] = newclss[i];
    
        prevlen = len;
        if(len==n) break;
        len = len*2;
        if(len>n) len = n;
    }


    // remove first element of pos
    pos.erase(pos.begin());
    return pos;

}

vector<int> lcp_array(const string&s, const vector<int>& sa){
    int n = s.size();
    vector<int> lcp(n-1,-1);
    vector<int> rank(n);
    for(int i=0; i<n; i++)rank[ sa[i] ] = i;

    // there are n suffixes
    // lcp[i] -> lcp of suffix[ sa[i] ] and suffix[ sa[i+1] ]

    for(int idx=0; idx<n; idx++){
        int i = rank[idx];
        if(i == n-1){
            continue;
        }
        if(lcp[i]==-1){
            int idx1 = sa[i];
            int idx2 = sa[i+1];
            int curlcp = 0;
            while(idx1<n && idx2<n && s[idx1]==s[idx2]){
                idx1++,idx2++,curlcp++;
            }
            // maybe 0,1,2...
            lcp[i] = curlcp;
            curlcp--;
            idx1 = sa[i]+1;
            idx2 = sa[i+1]+1;
            while(idx1<n && idx2<n && curlcp >= 0){
                int rank1 = rank[idx1];
                int rank2 = rank[idx2];
                if(rank2 != rank1+1){
                }
                else{
                    lcp[rank1] = curlcp;
                }
                
                curlcp--, idx1++, idx2++;
            }
        }
    }

    return lcp;
}

class PrefixSumSALengths{
public:
    vector<lli> psum;
    int n;

    PrefixSumSALengths(){

    }

    PrefixSumSALengths(const vector<int>& sa){
        this->n = sa.size();
        psum = vector<lli>(n+1, 0);
        for(int i=1; i<=n; i++){
            psum[i] = psum[i-1] + (n - sa[i-1]);
        }
    }

    lli get_sum(int st, int end) const{
        assert(end+1 <= n);
        assert(st>=0);
        return psum[end+1] - psum[st];
    }

};

namespace spt{
    const int MX = 27;
    const int SZ = 200000;
    int table[MX][SZ+1];
    struct rmq{
        int n;

        rmq(){}
        rmq(const vector<int>& arr){init(arr);}
        void init(const vector<int>& arr)
        {
            n = arr.size();
            assert(n <= SZ);
            for(int idx=0; (1<<idx)<=n; idx++){
                for(int i=0; i<n; i++){
                    if(idx==0){
                        table[idx][i] = arr[i];
                    }
                    else{
                        int sz = 1<<idx;
                        if(i+sz-1>=n) break;
                        table[idx][i] = min( table[idx-1][i], table[idx-1][i+sz/2]);
                    }
                }
            }
        }
        int getmin(int st, int end){
            
            // sz = (end-st+1)
            // start idx = st
            // __lg(sz)
            int idx = __lg(end-st+1) ;
            int pow2 = 1 << idx;
            int st2 = end - pow2 + 1;
            return min( table[idx][st] , table[idx][st2]);
        }
    };
}


string s;
lli k;
int n;
vector<int> sa;
vector<int> lcp;
PrefixSumSALengths psum;

string ans;
spt::rmq rmq;


int get_lcp(int i, int j){
    if(i==j){
        return n - sa[i];   
    }
    else{
        return rmq.getmin(i, j-1);
    }
}

int get_last(int i, int len){
    // ith rank
    // last guy j with lcp(i,j) >= len

    assert(lcp[i] >= len);

    int st = i;
    int end = n-1;

    int j = -1;
    while(st <= end)
    {
        int mid = (st+end)/2;
        if(get_lcp(i, mid)>=len && (mid==n-1 || get_lcp(i, mid+1)<len)){
            j = mid;
            break;
        }
        else if(get_lcp(i, mid) < len){
            end = mid-1;
        }
        else{
            st = mid+1;
        }
    }
    assert(j!=-1);
    return j;

}

void solve(){
    cin>>s>>k;
    n = s.size();

    sa = suffix_array(s);
    lcp = lcp_array(s, sa);
    lcp.push_back(0);

    rmq.init(lcp);
    int prevlcp = 0;
    for(int rank=0; rank<n; rank++){
        int idx = sa[rank];

        // Mistake 1 : did prevlcp instead of 'prevlcp + 1'

        int stlen = prevlcp + 1;
        int endlen = lcp[rank];

        for(int len = stlen; len<=endlen; len++){
            // string is s[idx...idx+len-1]
            int lastrank = get_last(rank, len);
            int cnt = lastrank - rank + 1;
            if(cnt >= k){
                ans = s.substr(idx, len);
                // Mistake 2 : did this after the break
                k = 0;
                break;
            }
            else{
                k -= cnt;
            }
        }

        if(k==0) break;

        // Mistake 3 : did not do this donelen
        int donelen = max(lcp[rank], prevlcp);
        int next_cnt = n - (idx + donelen) ;

        assert(next_cnt >= 0);

        if(next_cnt >= k){
            // Mistake 4 : did not used donelen here
            ans = s.substr(idx, donelen + k);
            break;
        }
        else{
            k -= next_cnt;
        }
        
        prevlcp = lcp[rank];
    }   

    cout << ans << endl;
}


int main(){


    #ifndef ONLINE_JUDGE
        dm = 1;
	#endif
    if(!dm)fastio();
    //fastio();
    fileio();

    lli tst=1;
        
    //if(dm)cin>>tst ;
    while(tst--){
        // input
        solve();
    }
    return 0 ;
}