Text Editor

题意翻译

给定两个字符串 $S, T$，初始时光标在串 $S$ 尾部，你可以进行以下操作： - $\texttt{left}$：将光标向左移动一个字符，如光标在字符串最左侧则不移动。 - $\texttt{right}$：将光标向右移动一个字符，如光标在字符串最右侧则不移动。 - $\texttt{home}$：将光标移动到字符串最左侧，如光标在字符串最左侧则不移动。 - $\texttt{end}$：将光标移动到字符串最右侧，如光标在字符串最右侧则不移动。 - $\texttt{backspace}$：将光标左侧的第一个字符从字符串中删除，如光标在字符串最左侧则不删除任何字符。 我们需要使 $S$ 在做若干次操作后得到 $T$，请你求出最小的操作次数。无解输出 $-1$。

题目描述

You wanted to write a text $ t $ consisting of $ m $ lowercase Latin letters. But instead, you have written a text $ s $ consisting of $ n $ lowercase Latin letters, and now you want to fix it by obtaining the text $ t $ from the text $ s $ . Initially, the cursor of your text editor is at the end of the text $ s $ (after its last character). In one move, you can do one of the following actions: - press the "left" button, so the cursor is moved to the left by one position (or does nothing if it is pointing at the beginning of the text, i. e. before its first character); - press the "right" button, so the cursor is moved to the right by one position (or does nothing if it is pointing at the end of the text, i. e. after its last character); - press the "home" button, so the cursor is moved to the beginning of the text (before the first character of the text); - press the "end" button, so the cursor is moved to the end of the text (after the last character of the text); - press the "backspace" button, so the character before the cursor is removed from the text (if there is no such character, nothing happens). Your task is to calculate the minimum number of moves required to obtain the text $ t $ from the text $ s $ using the given set of actions, or determine it is impossible to obtain the text $ t $ from the text $ s $ . You have to answer $ T $ independent test cases.

输入输出格式

输入格式

The first line of the input contains one integer $ T $ ( $ 1 \le T \le 5000 $ ) — the number of test cases. Then $ T $ test cases follow. The first line of the test case contains two integers $ n $ and $ m $ ( $ 1 \le m \le n \le 5000 $ ) — the length of $ s $ and the length of $ t $ , respectively. The second line of the test case contains the string $ s $ consisting of $ n $ lowercase Latin letters. The third line of the test case contains the string $ t $ consisting of $ m $ lowercase Latin letters. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 5000 $ ( $ \sum n \le 5000 $ ).

输出格式

For each test case, print one integer — the minimum number of moves required to obtain the text $ t $ from the text $ s $ using the given set of actions, or -1 if it is impossible to obtain the text $ t $ from the text $ s $ in the given test case.

输入输出样例

输入样例 #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

**题目大意**：

给定两个字符串 $S, T$，初始时编辑器的光标位于字符串 $S$ 的末尾。可以执行以下操作：

- `left`：将光标向左移动一个字符，如果光标已经在最左端则不移动。
- `right`：将光标向右移动一个字符，如果光标已经在最右端则不移动。
- `home`：将光标移动到字符串的最左端，如果光标已经在最左端则不移动。
- `end`：将光标移动到字符串的最右端，如果光标已经在最右端则不移动。
- `backspace`：删除光标左侧的第一个字符，如果光标已经在最左端则不删除任何字符。

目标是通过一系列操作使得字符串 $S$ 变为字符串 $T$。需要求出实现这个目标所需的最小操作次数。如果无法通过操作实现目标，则输出 `-1`。

**输入输出数据格式**：

**输入格式**：
- 第一行包含一个整数 $T$（$1 \le T \le 5000$），表示测试用例的数量。
- 每个测试用例包含三行：
- 第一行包含两个整数 $n$ 和 $m$（$1 \le m \le n \le 5000$），分别表示字符串 $S$ 和 $T$ 的长度。
- 第二行包含一个由 $n$ 个小写拉丁字母组成的字符串 $S$。
- 第三行包含一个由 $m$ 个小写拉丁字母组成的字符串 $T$。

**输出格式**：
- 对于每个测试用例，输出一行，包含一个整数，表示从字符串 $S$ 变为字符串 $T$ 所需的最小操作次数，或者如果无法实现，则输出 `-1`。**题目大意**： 给定两个字符串 $S, T$，初始时编辑器的光标位于字符串 $S$ 的末尾。可以执行以下操作： - `left`：将光标向左移动一个字符，如果光标已经在最左端则不移动。 - `right`：将光标向右移动一个字符，如果光标已经在最右端则不移动。 - `home`：将光标移动到字符串的最左端，如果光标已经在最左端则不移动。 - `end`：将光标移动到字符串的最右端，如果光标已经在最右端则不移动。 - `backspace`：删除光标左侧的第一个字符，如果光标已经在最左端则不删除任何字符。 目标是通过一系列操作使得字符串 $S$ 变为字符串 $T$。需要求出实现这个目标所需的最小操作次数。如果无法通过操作实现目标，则输出 `-1`。 **输入输出数据格式**： **输入格式**： - 第一行包含一个整数 $T$（$1 \le T \le 5000$），表示测试用例的数量。 - 每个测试用例包含三行： - 第一行包含两个整数 $n$ 和 $m$（$1 \le m \le n \le 5000$），分别表示字符串 $S$ 和 $T$ 的长度。 - 第二行包含一个由 $n$ 个小写拉丁字母组成的字符串 $S$。 - 第三行包含一个由 $m$ 个小写拉丁字母组成的字符串 $T$。 **输出格式**： - 对于每个测试用例，输出一行，包含一个整数，表示从字符串 $S$ 变为字符串 $T$ 所需的最小操作次数，或者如果无法实现，则输出 `-1`。