C++14(g++5.4) 解法, 执行用时: 82ms, 内存消耗: 7672K, 提交时间: 2020-04-17 21:58:37

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,k,r[N],p[N],q[N];
char c[N];
bool cmp(int x,int y){
	for(int i=0;i<k;i+=min(r[x+i]-x-i,r[y+i]-y-i)){
		if(c[x+i]!=c[y+i])return c[x+i]<c[y+i];
	}
	return 0;
}
int main(){
	scanf("%d %d %s",&n,&k,c+1);
	for(int i=1;i<=n;++i)c[i+n]=c[i];
	for(int i=n+n;i;i--){
		if(c[i]!=c[i+1])r[i]=i+1;
		else r[i]=r[i+1];
	}
	int l=n/k;
	for(int i=1;i<=k;++i){
		for(int o=1;o<=l;++o){
			p[o]=k*(o-1)+i;
		}
		sort(p+1,p+l+1,cmp);
		q[i]=p[l];
	}
	int z=1;
	for(int i=2;i<=k;++i){
		if(!cmp(q[z],q[i]))z=i;
	}
	for(int i=0;i<k;++i)putchar(c[q[z]+i]);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 90ms, 内存消耗: 16636K, 提交时间: 2020-04-17 19:48:35

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inc(i, l, r) for (int i = l; i <= r; i++)

const int maxn = 1e6 + 5;

string s;
int n, k;
string res = "~";

int main() {
    cin >> n >> k >> s;
    s.append(s.substr(0, n / k));
    vector<string> v(k, string(n / k, '0'));
    inc(del, 0, n / k - 1) {
        string tmp = "";
        inc(i, 0, k - 1) tmp = max(tmp, s.substr(n / k * i + del, n / k));
       // cout << tmp << "\n";
        res = min(res, tmp);
    }
    cout << res << "\n";
}