CF1231E Middle-Out

本题灵感来源于《吹笛人》的故事。在 Hooli 的压缩竞争对手 Nucleus 发起挑战后，Richard 熬夜发明了一种新的压缩方法：middle-out。 给定两个长度相同的字符串 $s$ 和 $t$，它们的字符从左到右编号为 $1$ 到 $n$（即从开头到结尾）。 每次操作你可以进行以下动作： - 选择任意一个合法的下标 $i$（$1 \le i \le n$）， - 将 $s$ 的第 $i$ 个字符移动到字符串的开头，或者将 $s$ 的第 $i$ 个字符移动到字符串的结尾。 注意，这些操作不会改变字符串 $s$ 的长度。你只能对字符串 $s$ 进行操作。 例如，若 $s=$ "test"，一次操作后可以得到： - 如果 $i=1$ 并且移动到开头，结果为 "test"（字符串不变）； - 如果 $i=2$ 并且移动到开头，结果为 "etst"； - 如果 $i=3$ 并且移动到开头，结果为 "stet"； - 如果 $i=4$ 并且移动到开头，结果为 "ttes"； - 如果 $i=1$ 并且移动到结尾，结果为 "estt"； - 如果 $i=2$ 并且移动到结尾，结果为 "tste"； - 如果 $i=3$ 并且移动到结尾，结果为 "tets"； - 如果 $i=4$ 并且移动到结尾，结果为 "test"（字符串不变）。 你希望通过最少的操作次数将字符串 $s$ 变为字符串 $t$。如果无法将 $s$ 变为 $t$，输出 $-1$。

第一行包含一个整数 $q$（$1 \le q \le 100$），表示输入中独立测试用例的数量。 每个测试用例包含三行。第一行为一个整数 $n$（$1 \le n \le 100$），表示字符串 $s$ 和 $t$ 的长度。第二行为字符串 $s$，第三行为字符串 $t$。$s$ 和 $t$ 均为长度为 $n$ 的仅包含小写拉丁字母的字符串。 测试用例中 $n$ 的总和没有限制（即允许 $q=100$ 且所有 $n=100$ 的输入）。

对于每个测试用例，输出将 $s$ 变为 $t$ 所需的最小操作次数。如果无法完成转换，输出 $-1$。

在第一个示例中，一种最优操作方案如下： - 对于第一个测试用例 $s=$ "iredppipe"，$t=$ "piedpiper"： "iredppipe" $\rightarrow$ "iedppiper" $\rightarrow$ "piedpiper"； - 对于第二个测试用例 $s=$ "estt"，$t=$ "test"： "estt" $\rightarrow$ "test"； - 对于第三个测试用例 $s=$ "tste"，$t=$ "test"： "tste" $\rightarrow$ "etst" $\rightarrow$ "test"。 由 ChatGPT 4.1 翻译