この問題は Suffix Tree をDFSすることで解くことができます。順に説明します

Suffix array

文字列 \(S\) の空でない接尾辞を辞書順にソートしたとき、各文字列が \(S\) の何文字目からの接尾辞であるかを表す配列を Suffix Array といいます。
例えば \(S\) が aabab のとき、\(S\) の suffix は aabab, abab, bab, ab, b であり、これらを辞書順にソートすると aabab, ab, abab, b, bab となります。これらはそれぞれ (0-indexed で) \(S\) の \(0,3,1,4,2\) 文字目からの接尾辞であるため、aabab の suffix array は \((0,3,1,4,2)\) となります。

Suffix array は適切な実装により \(O(|S|)\) 時間で求めることができます。

LCP array

\(S\) の suffix をソートした列において隣接する suffix の最長共通接頭辞 (Longest Common Prefix) の長さを表す配列を LCP array といいます。
例えば aabab の LCP array は \((1,2,0,1)\) となります。

LCP array は Suffix array をもとに適切な実装により \(O(|S|)\) 時間で求めることができます。

Suffix tree

\(S\) の全ての Suffix を持つ trie (を適切に縮約したもの)を suffix tree といいます。
例えば aabab の Suffix tree は下図のようになります。

Suffix tree の頂点数は \(O(|S|)\) であり、LCP array をもとに適切な実装により \(O(|S|)\) 時間で求めることができます。

Suffix tree 上の DFS

\(S\) Suffix tree を DFS することで、\(S\) の全ての部分文字列を辞書順に列挙することができます。ノードに適切に情報をもたせることで、列挙の代わりに数え上げを行うことができ、全体で \(O(N)\) 時間でこの問題を解くことができます。

実装例

以下の実装例は Suffix tree を明示的に構築せず、対応する suffix array の区間を状態として DFS をしており、次に探索するノードをセグメントツリーを用いて探しているため、計算量は \(O(N\log N)\) になっています。

実装例(C++)

#include<bits/stdc++.h>
#include<atcoder/string>
#include<atcoder/segtree>
using namespace std;
using ll=long long;

int op(int x,int y){return min(x,y);}
int e(){return 1e9;}

int main(){
	ll n,k;
	cin >> n >> k;
	k--;
	string s;
	cin >> s;

	auto sa=atcoder::suffix_array(s);
	auto lcpa=atcoder::lcp_array(s,sa);

	atcoder::segtree<int,op,e>seg(lcpa);

	auto dfs=[&](auto self,int l,int r,int prev_depth)->void{
		//l,rはsaのindex
		if(r-l==1){
			//葉ノード
			int count=n-sa[l]-prev_depth;
			if(k<count){
				cout << s.substr(sa[l],prev_depth+k+1) << endl;
				exit(0);
			}else{
				k-=count;
				return;
			}
		}

		// このノードを処理
		int depth=seg.prod(l,r-1);
		ll count=(ll)(r-l)*(depth-prev_depth);
		if(k<count){
			cout << s.substr(sa[l],prev_depth+k/(r-l)+1) << endl;
			exit(0);
		}else{
			k-=count;
		}

		//最小値を達成する index を取得
		auto f=[&](int x){return x>depth;};
		int m=seg.max_right(l,f);

		self(self,l,m+1,depth);
		self(self,m+1,r,depth);
	};

	dfs(dfs,0,n,0);
}

類題：ABC280Ex『Substring Sort』