已经和 @Alex_Wei 题解对拍许多组：

#include <bits/stdc++.h>
#define link __ytxy_ak_ioi
#define CLR(x) memset(x, 0, sizeof(x))
using namespace std;

const int N = 4e5 + 5, M = 10;

int trans[N << 1][M], link[N << 1], len[N << 1], cur, tot, endps[N], siz[N];

void extend(int c, int cnt){
	int x=cur;cur=(++tot);len[cur]=len[x]+1;endps[cnt] = cur;siz[cur] = 1;
	for(;(~x)&&(!trans[x][c]);x=link[x]) trans[x][c] = cur;
	if(!(~x)){link[cur]=0;return;}
	int y=trans[x][c];
	if(len[y]==len[x]+1){link[cur]=y;return;}
	int u=(++tot),d=y;
	link[u]=link[y];link[d]=link[cur]=u;len[u]=len[x]+1;
	for(int i=0;i<9;i++) trans[u][i] = trans[d][i];
	for(;(~x)&&(trans[x][c]==y);x=link[x]) trans[x][c] = u;
}

int n, k;
string s, s1;
bool vis[N << 1];
int lft[N << 1], rnk[N], rktt;
int son[N << 1], rev[N << 1], seg[N << 1], top[N << 1], sgtt = 1, dep[N << 1];
vector<int> ptr[N << 1];
vector<int> zyb[N << 1];

void count_siz(int u){
	for(int v : ptr[u]){
		count_siz(v);
		siz[u] += siz[v];
	}
}

int dfs1(int u){
	int szt = 1, tmp = 0;
	son[u] = 0;
	for(int v : ptr[u]){
		dep[v] = dep[u] + 1;
		int szv = dfs1(v);
		szt += szv;
		if(tmp < szv){
			tmp = szv;
			son[u] = v;
		}
	}
	return szt;
}

void dfs2(int u){
	if(son[u]){
		top[son[u]] = top[u];
		seg[son[u]] = ++sgtt;
		rev[sgtt] = son[u];
		dfs2(son[u]);
	}
	for(int v : ptr[u]){
		if(son[u] == v) continue;
		top[v] = v;
		seg[v] = ++sgtt;
		rev[sgtt] = v;
		dfs2(v);
	}
}

int find(int l, int r){
	int u = endps[r];
	while(true){
//		cout << u << ' ';
		if(!top[u] || len[link[top[u]]] < (r - l + 1)){
			int L = seg[top[u]], R = seg[u];
			while(L <= R){
				int mid = (L + R) >> 1;
                if(!(~link[rev[mid]])){
                    L = mid + 1;
                    continue;
                }
				if(len[link[rev[mid]]] < (r - l + 1)) L = mid + 1;
				else R = mid - 1;
			}
			L--;
//			cout << rev[L] << '\n';
			return rev[L];
		}
		u = link[top[u]];
	}
}

int length;

void dfs(int u){
	sort(ptr[u].begin(), ptr[u].end(), [&](int x, int y){
		return s1[lft[x] - 1] < s1[lft[y] - 1];
	});
	if(length <= len[u] && length > len[link[u]]){
		int rkt = rktt + 1;
		for(int i : zyb[u]){
			rnk[i] = rkt;
			rktt++;
		}
		return;
	}
	for(int v : ptr[u]) dfs(v); 
}


bool check(int x, bool dbg = 0){
	for(int i=1;i<=length;i++){
		int now = 0;
		for(int j=1;j<=k;j++){
			int p = (i + now - 1) % n + 1;
			if(rnk[p] <= x) now += length;
			else now += length - 1;
		}
//		if(dbg){
//			cout << '\n';
//		}
		if(now >= n) return true;
	}
	return false;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> k >> s;length = (n - 1) / k + 1;
	s1 = s + s;reverse(s1.begin(), s1.end());link[0] = -1;
	for(unsigned i=0;i<s1.size();i++) extend(s1[i] - '0' - 1, i + 1);
	for(unsigned i=1;i<=n;i++){
		int LFT = 0;
		for(int j=endps[i];j;j=link[j]){
			LFT += (len[j] - len[link[j]]);
			lft[j] = LFT;
			if(vis[j]) break;
			vis[j] = true;
		}
	}
	for(int i=1;i<=tot;i++) ptr[link[i]].push_back(i);
	count_siz(0);
	seg[0] = dep[0] = 1;top[0] = len[0] = 0;
	dfs1(0);dfs2(0);
	for(int i=1;i<=n;i++){
		int revt = i + length - 1;
		if(revt > n) revt -= n;
		revt = n - revt + 1;
		int u = find(i, i + length - 1);
//		cout << u << ' ' << len[u] << ' ' << len[link[u]] << '\n';
		zyb[find(i, i + length - 1)].push_back(revt);
	}
//	cout << "------------------------------------\n";
	dfs(0);
//	for(int i=1;i<=rktt;i++) cout << rnk[i] << ' ';cout<<'\n';
//	cout << "------------------------------------\n";
	int L = 1, R = n;
	while(L < R){
		int mid = (L + R) >> 1;
		if(check(mid)) R = mid;
		else L = mid + 1;
	}
	reverse(s1.begin(), s1.end());
//	cout << L << ' ' << check(L) << '\n';
//	check(L, 1);
	int fir = 0;
	for(int i=1;i<=n;i++){
		if(rnk[i] == L){
			fir = i;
			break;
		}
	}
//	cout << fir << '\n';
	for(int i=0;i<length;i++) cout << s1[(fir + i - 1)];
	return 0;
}

/*
10 9
4363593573
*/

/*
7 5
7183782
*/