CF2164D Copy String

给定两个长度为 $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$ 的字符串，即每次操作后的字符串。 如果有多种方案，输出任意一种均可。

在第一个测试用例中，显然 $s$ 可以在一次操作内变成 $t$。 在第二个测试用例中，最开始就有 $s=t$，因此不需要任何操作。 在第四个测试用例中，虽然 $s$ 可以通过两次操作变成 $t$，但是 $k_{\mathrm{max}}=1$，因此答案为 -1。 由 ChatGPT 5 翻译