← 返回题目列表

Codeforces · 1701/E

E. 文本编辑器

中文机器翻译题面 查看原题

您想要编写由 $$$m$$$ 小写拉丁字母组成的文本 $$$t$$$。相反,您编写了由 $$$n$$$ 小写拉丁字母组成的文本 $$$s$$$,现在您想通过从文本 $$$s$$$ 获取文本 $$$t$$$ 来修复它。

最初,文本编辑器的光标位于文本 $$$s$$$ 的末尾(在其最后一个字符之后)。您可以一步执行以下操作之一:

- 按“向左”按钮,使光标向左移动一个位置(或者如果光标指向文本的开头,即第一个字符之前,则不执行任何操作);
- 按“向右”按钮,使光标向右移动一个位置(或者如果光标指向文本末尾,即在最后一个字符之后,则不执行任何操作);
- 按“home”按钮,使光标移动到文本的开头(文本的第一个字符之前);
- 按“结束”按钮,使光标移动到文本末尾(文本最后一个字符之后);
- 按“退格”按钮,因此光标之前的字符将从文本中删除(如果没有该字符,则不会发生任何情况)。

你的任务是计算使用给定的一组动作从文本$$$s$$$获取文本$$$t$$$所需的最小移动次数,或者确定不可能从文本$$$s$$$获取文本$$$t$$$。

您必须回答 $$$T$$$ 独立测试用例。

输入

输入的第一行包含一个整数 $$$T$$$ ($$$1 \le T \le 5000$$$) — 测试用例的数量。然后是 $$$T$$$ 测试用例。

测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le m \le n \le 5000$$$) — 分别是 $$$s$$$ 的长度和 $$$t$$$ 的长度。

测试用例的第二行包含由 $$$n$$$ 小写拉丁字母组成的字符串 $$$s$$$。

测试用例的第三行包含由 $$$m$$$ 小写拉丁字母组成的字符串 $$$t$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$ ($$$\sum n \le 5000$$$)。

输出

对于每个测试用例,打印一个整数 — 使用给定的一组操作从文本 $$$s$$$ 获取文本 $$$t$$$ 所需的最小移动次数,如果在给定测试用例中无法从文本 $$$s$$$ 获取文本 $$$t$$$,则打印 -1。

示例

输入 #1

6
9 4
aaaaaaaaa
aaaa
7 3
abacaba
aaa
5 4
aabcd
abcd
4 2
abba
bb
6 4
baraka
baka
8 7
question
problem

输出 #1

5
6
3
4
4
-1