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; }