如何优雅的写单词_lduoj_kmp

如何优雅的写单词

Description

单词背多少了！？

心里还没有点数了！？

还有多长时间考试你知道吗！？

你说，单词背到第几章了！？

呜呜呜，别骂了别骂了，再骂人傻了

在深知单词的重要性之后，PushyTao下定决心要好好背单词。为了防止在考试的时候不会写，PushyTao还决定在背单词的时候还要写几遍，但是他太懒了，所以就“发明”出了一种新的方法：

比如说，对于一个长度为n的单词，PushyTao要写m遍。如果这个单词的后半部分和前面的一部分有相同，他就会省略掉相同的不写。比如说长度为3的一个单词aba，PushyTao要写4遍，那么就可以将单词写成ababababa，因为从s[1] ~ s[3]，从s[3] ~ s[5]，从s[5] ~ s[7]，从s[7]~s[9]都是aba，所以这样PushyTao就非常“巧妙的”写完了4遍单词；但是也有让PushyTao很无语的单词，比如abc，就不得不写成abcabcabcabc

Input

第一行：一个整数n代表单词的长度，一个整数m，代表要写的次数（1<=n,m<=50）

第二行：一个长度为n的字符串

Output

输出一个字符串，代表PushyTao可以写的长度最短的一个字符串

Samples

Input 复制

3 4
aba

Output

ababababa

Input 复制

3 2
abc

Output

abcabc

这个题的原型是CF 这个题

相关的题解可以看一下，我现在写一下这个题的题解

看一下数据范围可以看出来，这个题可以直接硬生生的进行模拟，可以便利字符串寻找长度最长的前缀和后缀，然后输出就可以。

说到这里，聪明的小伙伴已经发现了，在KMP中next数组不就可以用在最长的公共前后缀嘛

所以说这个题直接可以先输出一个原先的字符串，然后对于剩下的m-1次直接输出从next[n] ~ n-1的每一个字符串就好了嘛(下标从0开始)

优雅的KMP_Code():

char p[107];
int n,k;
int nex[107];
void _get_next(){
    nex[0] = 0;
    nex[1] = 0;
    for(int j=1;j<n;j++){
        int k = nex[j];
        while(k && p[j] != p[k]) k = nex[k];
        if(p[j] == p[k]) nex[j+1] = k+1;
        else nex[j+1] = 0;
    }
}
int main() {
    cin >> n >> k;
    cin >> p;
    _get_next();
    cout<<p;
    k--;
    while(k --){
        for(int i=nex[n];i<n;i++) printf("%c",p[i]);
    }
  return 0;
}