图片说明
图片说明 

哈希：
#include <bits/stdc++.h>
using namespace std;
#define  LL long long
const int maxn=1e6+10;

LL mod[2]= {1610612741, 998244353};
LL base[2] ={131, 233};
LL p[2][maxn];
LL g[2][maxn];

void getp(){
    p[0][0]=p[1][0]=1;
    for(int i=1; i<maxn; i++){
        p[0][i]=p[0][i-1]*base[0]%mod[0];
        p[1][i]=p[1][i-1]*base[1]%mod[1];
    }
}

pair<LL, LL> Hash(char s[]){
    int len=strlen(s+1);
    g[0][0]=0, g[0][1]=s[1];
    g[1][0]=0, g[1][1]=s[1];
    for(int i=2; i<=len; i++){
        g[0][i]=(g[0][i-1]*base[0]+s[i])%mod[0];
        g[1][i]=(g[1][i-1]*base[1]+s[i])%mod[1];
    }
    return {g[0][len], g[1][len]};
}

pair<LL, LL> getLR(int l, int r){
    LL ans1=((g[0][r]-g[0][l-1]*p[0][r-l+1])%mod[0]+mod[0])%mod[0];
    LL ans2=((g[1][r]-g[1][l-1]*p[1][r-l+1])%mod[1]+mod[1])%mod[1];
    return {ans1, ans2};
}

char s[maxn];
int pos[maxn];

int solve(int x, int y, int k){
    int l=0, r=k, pos=0;
    while(l<=r){
        int mid=(l+r)/2;
        if(getLR(x, x+mid-1)==getLR(y, y+mid-1)){
            l=mid+1; pos=mid;
        }
        else{
            r=mid-1;
        }
    }
    if(s[x+pos]<s[y+pos]) return 1;
    else return 0;
}

int main(){
    getp();
    int n, k; scanf("%d%d%s", &n, &k, s);
    for(int i=0; i<n; i++){
        s[n+i]=s[i];
    }
    Hash(s);
    for(int i=0; i<n; i++){
        if(i<k) pos[i%k]=i;
        else{
            if(solve(pos[i%k], i, k)){
                pos[i%k]=i;
            }
        }
    }
    int ans=pos[0];
    for(int i=1; i<k; i++){
        if(!solve(ans, pos[i], k)){
            ans=pos[i];
        }
    }
    for(int i=0; i<k; i++){
        printf("%c", s[ans+i]);
    }
    printf("\n");

    return 0;
}

后缀数组
#include <iostream>
#include<algorithm>
#include <stdio.h>
#include <string.h>
using namespace std;
#define maxn 1000005
int wa[maxn],wb[maxn],wsf[maxn],wv[maxn],sa[maxn];
int rak[maxn],height[maxn], s[maxn];
char s1[maxn];

//sa:字典序中排第i位的起始位置在str中sa[i]  sa[1~n]为有效值
//rank:就是str第i个位置的后缀是在字典序排第几 rank[0~n-1]为有效值
//height：字典序排i和i-1的后缀的最长公共前缀  height[1~n]为有效值，第1个到最后一个

int cmp(int *r,int a,int b,int k)
{
    return r[a]==r[b]&&r[a+k]==r[b+k];
}
void getsa(int *r,int *sa,int n,int m){//n为添加0后的总长
    int i,j,p,*x=wa,*y=wb,*t;
    for(i=0; i<m; i++)  wsf[i]=0;
    for(i=0; i<=n; i++)  wsf[x[i]=r[i]]++;
    for(i=1; i<m; i++)  wsf[i]+=wsf[i-1];
    for(i=n; i>=0; i--)  sa[--wsf[x[i]]]=i;
    p=1;
    j=1;
    for(; p<=n; j*=2,m=p)
    {
        for(p=0,i=n+1-j; i<=n; i++)  y[p++]=i;
        for(i=0; i<=n; i++)  if(sa[i]>=j)  y[p++]=sa[i]-j;
        for(i=0; i<=n; i++)  wv[i]=x[y[i]];
        for(i=0; i<m; i++)  wsf[i]=0;
        for(i=0; i<=n; i++)  wsf[wv[i]]++;
        for(i=1; i<m; i++)  wsf[i]+=wsf[i-1];
        for(i=n; i>=0; i--)  sa[--wsf[wv[i]]]=y[i];
        t=x;
        x=y;
        y=t;
        x[sa[0]]=0;
        for(p=1,i=1; i<=n; i++)
            x[sa[i]]=cmp(y,sa[i-1],sa[i],j)? p-1:p++;
    }
}
void getheight(int *r,int n)//n为添加0后的总长
{
    int i,j,k=0;
    for(i=1; i<=n; i++)  rak[sa[i]]=i;
    for(i=0; i<n; i++)
    {
        if(k)
            k--;
        else
            k=0;
        j=sa[rak[i]-1];
        while(r[i+k]==r[j+k])
            k++;
        height[rak[i]]=k;
    }
}

void pus(int len){
    puts("--------------All Suffix--------------");
    for (int i = 0; i < len; ++i)
    {
        printf("%d:\t", i);
        for (int j = i ; j < len; ++j)
            printf("%c", s1[j]);
        puts("");
    }

    puts("");
    puts("-------------After sort---------------");
    for (int i = 1; i <= len; ++i)
    {
        printf("sa[%2d ] = %2d\t", i, sa[i]);
        for (int j = sa[i]; j < len; ++j)
            printf("%c", s1[j]);
        puts("");
    }

    puts("");
    puts("---------------Height-----------------");
    for (int i = 1; i <= len; ++i)
        printf("height[%2d ]=%2d \n", i, height[i]);
    puts("");

    puts("----------------Rank------------------");
    for (int i = 0; i < len; ++i)
        printf("Rank[%2d ] = %2d\n", i, rak[i]);
    puts("------------------END-----------------");
}

int mx[maxn], pos[maxn];
int main()
{
    int n, k; scanf("%d%d%s", &n, &k, s1);
    int len=strlen(s1), tot=0;
    for(int i=0; i<len; i++){
        s1[len+i]=s1[i];
    }
    len*=2;
    for(int i=0; i<len; i++){
        s[tot++]=s1[i]-'a'+1;
    }
    s[tot]=0;

    getsa(s,sa,tot,5000);
    getheight(s,tot);
    //pus(tot);

    for(int i=0; i<len; i++){
        if(rak[i]>mx[i%k]){
            mx[i%k]=rak[i];
            pos[i%k]=i;
        }
    }

    int ans=pos[0];
    for(int i=1; i<k; i++){
        if(rak[pos[i]]<rak[ans]){
            ans=pos[i];
        }
    }

    for(int i=ans; i<ans+k; i++){
        printf("%c", s1[i]);
    }
    printf("\n");

    return 0;
}