CF1029A Many Equal Substrings

    • 153通过
    • 272提交
  • 题目来源 CodeForces 1029A
  • 评测方式 RemoteJudge
  • 标签 KMP 字符串 构造
  • 难度 普及/提高-
  • 时空限制 1000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    题目描述:

    你有一个字符串t,它由n个字母组成。

    定义一个字符串s的子串为s[l...r],表示从位置l到r构成的一个新的串。

    你的目标是构造一个字符串s,使得它的可能长度最小,要求s中存在k个位置i,可以找到k个以i为出发点的子串t。

    输入: 第一行输入两个整数n和k,表示t的长度和需要k个子串

    第二行输入字符串t

    输出:

    输出满足条件的长度最小的s。题目保证答案唯一。

    题目描述

    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 $ to $ r $ as $ 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.

    输入输出格式

    输入格式:

    The first line of the input contains two integers $ n $ and $ k $ ( $ 1 \le n, k \le 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.

    输出格式:

    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.

    输入输出样例

    输入样例#1: 复制
    3 4
    aba
    
    输出样例#1: 复制
    ababababa
    
    输入样例#2: 复制
    3 2
    cat
    
    输出样例#2: 复制
    catcat
    
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。