solution

其实本题只要解决一个问题，剩下的就是模拟了。

这个问题就是如何快速的比较两个字符串的字典序。这是一个非常经典的思路。我们对这两个字符串都哈希一遍，然后二分一下这两个字符串最长的公共前缀长度。然后比较最长公共前缀的下一位上的字符就行了。因为所有要比较的字符串都在同一个母串上。我们只要对这个母串进行一遍哈希就行了。

剩下的按照题目中讲的模拟即可。

code

/*
* @Author: wxyww
* @Date:   2020-04-17 19:15:03
* @Last Modified time: 2020-04-17 19:23:46
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1000010;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1; c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0'; c = getchar();
    }
    return x * f;
}
char s[N];

ull hs[N],base[N],B = 28;

int n,K,now[N];
ull get(int l,int r) {
    return hs[r] - hs[l - 1] * base[r - l + 1];
}
int check(int x,int y) {
    int l = 1,r = K,ans = 0;
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(get(x,x + mid - 1) == get(y,y + mid - 1)) ans = mid,l = mid + 1;
        else r = mid - 1;
    }
    return s[x + ans] < s[y + ans]; 
}

int main() {
    n = read(),K = read();
    scanf("%s",s + 1);

    for(int i = n + 1;i <= n + n;++i)
        s[i] = s[i - n];

    base[0] = 1;
    for(int i = 1;i <= n + n;++i) {
        hs[i] = hs[i - 1] * B + s[i] - 'a' + 1;
        base[i] = base[i - 1] * B;
    }

    for(int i = 1;i <= n;++i) {
        if(!now[i % K]) now[i % K] = i;
        else {
            if(check(now[i % K],i)) now[i % K] = i;
        }
    }
    int ans = now[0];
    for(int i = 1;i < K;++i) {
        if(check(now[i],ans)) ans = now[i];
    }


    for(int i = ans;i <= ans + K - 1;++i)
        putchar(s[i]);

    return 0;
}