Codeforces-1029A Many Equal Substrings

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.

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

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

13 − 4 =