Codeforces Round #506 (Div. 3) A Many Equal Substrings (cf 1029A)

题目：Many Equal Substrings

题意：给出一个字符串$t$，求一个最短的字符串$s$，使得$s$中恰好包含$k$个$t$。

思路：
可以看出，$k$个字符串$t$是有公共部分的，即$t$的最长公共前后缀长度（意义等同于$kmp$算法中的$next$数组）。
由于数据范围极小，可以暴力求出$t$的最长公共前后缀，计作$l$。
答案就是$k-1$个$l$加上一个$t$。

代码：

#include<bits/stdc++.h>
using namespace std;#define ll long long
#define inf (1<<30)
#define maxn 50int n,k;
char a[maxn+5];void read(int& x) {scanf("%d",&x);
}int main() {read(n);read(k);scanf("%s",a+1);int len=0;for(int i=1;i<n;i++) {for(int j=1;j<=i;j++) {if(a[j]!=a[n-i+j]) goto END;}len=i;END:;}for(int i=1;i<k;i++) {for(int j=1;j<=n-len;j++) printf("%c",a[j]);}printf("%s",a+1);return 0;
}