相等子串构造(Many Equal Substrings)

题目描述

给定一个由 $n$ 个小写拉丁字母组成的字符串 $t$，以及一个整数 $k$。

我们定义字符串 $s$ 的子串 $s[l \dots r]$ 表示从第 $l$ 个字符到第 $r$ 个字符的子串。

你的任务是构造一个最短的字符串 $s$，使得恰好有 $k$ 个位置 $i$ 满足 $s[i \dots i + n - 1] = t$。换句话说，你需要构造一个最短的字符串 $s$，使得恰好有 $k$ 个子串等于 $t$。

保证答案唯一。

输入格式

输入的第一行包含两个整数 $n$ 和 $k$（$1 \le n, k \le 50$），分别表示字符串 $t$ 的长度和子串的个数。

第二行包含一个长度恰好为 $n$ 的字符串 $t$，由小写拉丁字母组成。

输出格式

输出一个最短的字符串 $s$，使得恰好有 $k$ 个子串等于 $t$。

保证答案唯一。

样例输入 #1

3 4
aba

样例输出 #1

ababababa

样例输入 #2

3 2
cat

样例输出 #2

catcat

数据范围

由 ChatGPT 4.1 翻译

知识点与难度

本题涉及的知识点从属于 GESP 8级，难度（CF Rating）：1300。

测试点分布

出处：原题链接