Codeforces-1029A Many Equal Substrings

2018年9月7日 0条评论 425次阅读 0人点赞于衡

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

s

with indices from

l

r

s [l \dots r]

.
Your task is to construct such string

s

of minimum possible length that there are exactly

k

positions

i

such that

s [i \dots i + n - 1] = t

. 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

t

.It is guaranteed that the answer is always unique.

Input

The first line of the input contains two integers $n$ and $k$ ( $1 \leq n, k \leq 50$ ) — the length of the string $t$ and the number of substrings.

The second line of the input contains the string $t$ consisting of exactly $n$ lowercase Latin letters.

Output

Print such string $s$ of minimum possible length that there are exactly $k$ substrings of $s$ equal to $t$ .

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