Loading... ## 构造字符串 给定一个长度为 **n** 的由小写字母构成的字符串 **t** 以及一个整数 **k** 。 请你构造一个字符串 **s** ，要求： 1. 字符串 **s** 恰好有 **k** 个子串等于字符串 **t** 。 2. 字符串 **s** 的长度尽可能短。 保证一定存在唯一解。 ## 输入格式 第一行包含两个整数 **n** , **k** 。 第二行包含一个长度为 **n** 的由小写字母构成的字符串 **t** 。 ## 输出格式 输出满足条件的字符串 **s** 。 保证一定存在唯一解。 ## 数据范围 前 **3** 个测试点满足 **1** ≤ **n** , **k** ≤ **4** 。 所有测试点满足 **1** ≤ **n** , **k** ≤ **50** 。 ## 输入样例1： ``` 3 4 aba ``` ## 输出样例1： ``` ababababa ``` ## 输入样例2： ``` 3 2 cat ``` ## 输出样例2： ``` catcat ``` ## 思路 求出 KMP 中`next`数组，`next`中最后一位即是`str`循环的起点，第一次循环需特判 ## AC代码 ```cpp #include <bits/stdc++.h> using namespace std; const int N = 55; int n, m, idx, k, ne[N]; char str[N]; int main(){ cin >> n >> k >> str + 1; for (int i = 2, j = 0; i <= n; i++) { while (j && str[j + 1] != str[i]) j = ne[j]; if (str[j + 1] == str[i]) j++; ne[i] = j; } for (int i = 1; i <= n; i++) cout << str[i]; for (int i = 2, j = ne[n] + 1; i <= k; i++) { while (j <= n) cout << str[j++]; j = ne[n] + 1; } return 0; } ``` ``` Last modification：February 12, 2023 © Allow specification reprint Like 0 如果觉得我的文章对你有用，请随意赞赏
Comment here is closed