IOIP 20240303 shift-and-reverse - 题目

破解保险柜

Gru 需要破解 Vector 的保险柜，里面存放着专门为偷取月球任务设计的火箭图纸。这显然不是一件容易的任务，所以不应该交给 Minions 去做。因此，你需要解决这个问题。

密码锁有一个屏幕，屏幕上当前显示一个由小写英文字母组成的字符串 $s$。Vector 最喜欢的单词是一个与 $s$ 等长的字符串 $t$。Gru 确信，当屏幕上显示的字符串从 $s$ 变为 $t$ 时，锁就会打开。

屏幕旁边有一个输入整数的区域和一个按钮。Neferio 博士分析了这个装置，并告诉 Gru 和你：可以在区域中输入一个 $1$ 到 $|s|$ 之间的整数，按下按钮后：

字符串 $s$ 被分为前缀 $p$（长度为 $|s| - x$，即 $s$ 的前 $|s|-x$ 个字符）和后缀 $q$（长度为 $x$，即剩下的 $x$ 个字符），其中 $x$ 是输入的整数；
然后 $s$ 被替换为 $\overline{q^{\mathtt{rev}}p}$，即反转后的 $q$ 与 $p$ 拼接。

换句话说，长度为 $x$ 的后缀被反转后移到字符串的开头。例如，输入数字 $2$ 并按下按钮，字符串 arkshs 会变为 sharks。

显然，过多的按键操作会引起怀疑，增加被抓住的风险，因此操作次数是有限的。你需要找到一种方式，使用不超过 $m$ 次操作，在屏幕上得到字符串 $t$。

第一行包含两个整数 $n$ 和 $m$ —— 字符串 $s$ 和 $t$ 的长度，以及最大操作次数（$1 \le n \le 2000$；$5100 \le m \le 10^4$）。

第二行和第三行分别给出 $s$ 和 $t$，由 $n$ 个小写英文字母组成（字符从 a 到 z）。

如果无法从 $s$ 得到 $t$，且使用不超过 $m$ 次操作，则输出唯一的一个数 -1。

否则，第一行输出操作次数 $k$（$0 \le k \le m$），第二行输出 $k$ 个空格分隔的整数，其中第 $i$ 个数是第 $i$ 次操作前应输入的数字。

注意，不需要最小化操作次数，只需满足限制条件即可。

子任务	分值	限制	必需子任务	评测信息
0	–	样例	无	完全
1	9	$n \le 8$, $m = 10^4$	0	完全
2	21	$n \le 100$, $m = 10^4$	0, 1	首次错误
3	24	$n \le 1000$, $m = 10^4$	0–2	首次错误
4	12	$m = 10^4$	0–3	首次错误
5	12	$m \ge 8100$	0–4	首次错误
6	11	$m \ge 6100$	0–5	首次错误
7	11	无额外限制	0–6	首次错误

输入

6 10000
xyxzyy
yxyzyx

输出

4
6 3 2 3

输入

4 10000
xyzy
xyyx

输出

-1

在第一个样例中，经过操作后屏幕上的字符串变化如下：