CF1701E Text Editor

你本来想写一个由 $m$ 个小写拉丁字母组成的文本 $t$，但实际上你写成了一个由 $n$ 个小写拉丁字母组成的文本 $s$，现在你想通过编辑操作将 $s$ 变成 $t$。 一开始，文本编辑器的光标位于文本 $s$ 的末尾（即最后一个字符之后）。每次操作，你可以进行以下操作之一： - 按下“左”键，将光标向左移动一个位置（如果光标已经在文本开头，即第一个字符之前，则无效）； - 按下“右”键，将光标向右移动一个位置（如果光标已经在文本末尾，即最后一个字符之后，则无效）； - 按下“Home”键，将光标移动到文本开头（即第一个字符之前）； - 按下“End”键，将光标移动到文本末尾（即最后一个字符之后）； - 按下“Backspace”键，删除光标前的一个字符（如果前面没有字符，则无效）。 你的任务是计算，使用上述操作，将文本 $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$。

由 ChatGPT 4.1 翻译