You are given a string t consisting of n lowercase Latin letters and an integer number k.Let’s define a substring of some string with indices from to r as .
Your task is to construct such string s of minimum possible length that there are exactly k positions i such that . In other words, your task is to construct such string s of minimum possible length that there are exactly k substrings of s equal to .It is guaranteed that the answer is always unique.
Your task is to construct such string s of minimum possible length that there are exactly k positions i such that . In other words, your task is to construct such string s of minimum possible length that there are exactly k substrings of s equal to .It is guaranteed that the answer is always unique.
Input
The first line of the input contains two integers n and k (1≤n,k≤50) — the length of the string t and the number of substrings.
The second line of the input contains the string consisting of exactly n lowercase Latin letters.
Output
Print such string s of minimum possible length that there are exactly substrings of s equal to .
It is guaranteed that the answer is always unique.
Examples
input
Copy
3 4
aba
output
Copy
ababababa
input
Copy
3 2
cat
output
Copy
catcat
贪心:求出最大循环，然后把循环输出k次，最后补齐作为结束的字符串
注意：string::substr的使用，贪心策略的选取，以及枚举以长度枚举寻找最早的循环字母的方法。
#include<iostream>
#include<string>
using namespace std;
bool flag=true;
int main()
{
int n=0,k=0;//n: lenth of string,k construct sub
string start,aim;
cin>>n>>k;
cin>>start;
int i=1;
for(i=1;i<=n;i++)//lenth of 重复字段
{
flag=true;
for(int j=0;i+j<start.length();j++)
{
if(start.at(j)!=start.at(j+i))
{
flag=false;
break;
}
}
if(flag) break;//周期为i
}
string out=start.substr(0,i);
string out2=start.substr(i);
for(int num=0;num<k;num++)
{
cout<<out;
}
cout<<out2<<endl;
}