A16758 | $Copy String$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定两个长度为 $n$ 的字符串 $s$ 和 $t$，你需要通过一系列以下操作将 $s$ 变换为 $t$： - 构造一个新的长度为 $n$ 的字符串 $s'$，其中 $s'_1 = s_1$。对于每个 $1 < i \le n$，$s'_i$ 可以是 $s_i$ 或 $s_{i-1}$。然后用 $s'$ 替换 $s$。 你的任务是用最少的操作次数完成这个变换，并在每一步输出构造后的字符串 $s'$。如果无法在不超过 $k_{\mathrm{max}}$ 次操作内实现该变换，则输出 -1。

每个测试包含多组数据。第一行输入一个整数 $t$（$1\le t\le 10^4$），表示测试组数。 每组测试用以下形式描述： 第一行输入两个整数 $n$、$k_{\mathrm{max}}$（$1\le n\cdot k_{\mathrm{max}}\le 10^6$），分别表示字符串的长度和最多允许操作的次数。 第二行输入一个长度为 $n$ 的字符串 $s$。 第三行输入一个长度为 $n$ 的字符串 $t$。 保证所有测试数据中 $\sum nk_{\mathrm{max}}\le 10^6$。 保证 $s$ 和 $t$ 都只包含小写拉丁字母。

对于每组测试数据： - 若无法在不超过 $k_{\mathrm{max}}$ 次操作内将 $s$ 变换为 $t$，则输出一行 -1。 - 否则，第一行输出一个整数 $k\le k_{\mathrm{max}}$，表示最少所需操作次数。接下来的 $k$ 行，每行输出操作后的长度为 $n$ 的字符串，即每次操作后的字符串。 如果有多种方案，输出任意一种均可。

输入 #1

7
4 1
abcd
aabd
2 2
ab
ab
5 3
abcde
abbcc
9 1
egcnyeluw
eegccyelw
10 3
vzvylxxmsy
vvvvvllxxx
4 6
acba
aaac
5 7
acabb
aaaca

输出 #1

1
aabd
0
2
abbcd
abbcc
-1
3
vvzvylxxms
vvvzvllxxm
vvvvvllxxx
2
aacb
aaac
2
aacab
aaaca

C++ 编辑器

输入

输出