C++(g++ 7.5.0) 解法, 执行用时: 25ms, 内存消耗: 10096K, 提交时间: 2023-05-28 22:38:12

#include <cstdio>
#include <cstring>
using namespace std;
constexpr int maxn = 1000000 + 10;
char s[maxn];
int kmp[maxn], bin[maxn];
int main()
{
    int n, k;
    scanf("%d%d%s", &n, &k, s+1);
    for (int i=2,j=0;i<=n;++i)
    {
        while (j && s[j+1] != s[i]) j = kmp[j];
        if (s[j+1] == s[i]) ++j;
        kmp[i] = j;
    }
    for (int i=n;i>=1;--i) ++bin[i], bin[kmp[i]] += bin[i];
    /*for (int i=kmp[n];i;i=kmp[i])
        if (bin[i] >= k)
            return s[i+1] = 0, puts(s + 1), 0;
    */
    int u = n;
    while (bin[u] < k) u = kmp[u];
    if (u == 0) puts("-1");
    else for (int i=1;i<=u;++i) putchar(s[i]);
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 45ms, 内存消耗: 10132K, 提交时间: 2023-05-25 11:06:11

#include<iostream>
using namespace std;
const int N=2e6;
char str[N];
int n,k,nx[N];
int sz[N];
int main()
{
    scanf("%d%d",&n,&k);
    scanf("%s",str+1);
    for(int i=2,j=0;i<=n;i++)
    {
        while(j&&str[j+1]!=str[i]) j=nx[j];
        if(str[j+1]==str[i]) j++;
        nx[i]=j;
    }
    for(int i=n;i>=1;i--)
    {
        sz[i]++;
        sz[nx[i]]+=sz[i];
    }
    int u=n;
    while(sz[u]<k)
    {
        u=nx[u];
    }
    if(u==0) cout<<"-1"<<endl;
    else for(int i=1;i<=u;i++) cout<<str[i];
    return 0;
}