题目描述：

你有一个字符串t，它由n个字母组成。

定义一个字符串s的子串为\(s[l...r]\)，表示从位置l到r构成的一个新的串。

你的目标是构造一个字符串s，使得它的可能长度最小，要求s中存在k个位置i,可以找到k个以i为出发点的子串t。

输入： 第一行输入两个整数n和k，表示t的长度和需要k个子串

第二行输入字符串t

输出：

输出满足条件的长度最小的s。题目保证答案唯一。

思路分析

要构造出一个字符串 s ，使得里面出现 k 次 t，而且要求 s 尽可能短。要达到这个要求，有种贪心的感觉，我们希望尽可能利用上一个t的后缀来充当下一个t的前缀，也就是我们想知道t的最长相等前后缀。然后，这不就是next数组的含义嘛....所以我们得到如下算法：先构建字符串t的next数组，然后从j = 0开始，每次加入t[j+1],之后 j ++,如果 j == n,我们就跳回 j = ne[j],然后计数加一，如果计数 == k就结束构造，输出字符串s。

AC CODE

#include <iostream>

using namespace std;

const int N = 55;

int n,k;

int ne[N];

char t[N];

int main(){
    cin>>n>>k;
    scanf("%s",t+1);
    for(int i = 2, j = 0; i <= n;i++){
        while(j && t[j+1] != t[i]) j = ne[j];
        if(t[j+1] == t[i]) j++;
        ne[i] = j;
    }
    
    string s;
    int cnt = 0;
    int j = 0;
    while(cnt < k){
        s += t[j+1];
        j ++;
        if(j == n){
            j = ne[j];
            cnt ++;
        }
    }
    cout<<s<<endl;
    
    return 0;
}