← 返回题目列表

Codeforces · 2196/E1

E1. 模糊串联(简单版)

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

这是问题的简单版本。版本之间的区别在于,在这个版本中,$$$n \le 10^{5},m \le 10^{4}$$$。只有解决了该问题的所有版本,您才能破解。

有两个字符串 $$$s$$$ 和 $$$t$$$,均由小写拉丁字母组成。您还有一个空字符串 $$$p$$$。

您可以执行以下操作,该操作由多个阶段组成:

  • 选择任意两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le |s|$$$);
  • 复制子字符串 $$$s_{l},\ldots, s_{r}$$$ 并将其附加到字符串 $$$p$$$ 的末尾;
  • 在字符串 $$$p$$$ 的最后 $$$r - l + 1$$$ 个字符中,更改 最多 1 个 字符为任何小写拉丁字母。

例如,如果字符串 $$$s =$$$ "dhhtyhwbsl" 和 $$$p =$$$ "", 您可以选择 $$$l = 3, r = 6$$$ 并添加 "htyh“到$$$p$$$末尾,然后更改字符”y“到”a“,导致$$$p =$$$”哈".

您的任务是确定字符串 $$$p$$$ 等于 $$$t$$$ 所需的最少操作数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 10^{5}$$$, $$$1 \le m \le 10^{4}$$$) - 字符串 $$$s$$$ 和 $$$t$$$ 的长度。

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

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

保证所有测试用例的$$$n$$$总和不超过$$$10^{5}$$$,所有测试用例的$$$m$$$总和不超过$$$10^{4}$$$。

输出

对于每个测试用例,输出一个整数 - 问题的答案。

示例

输入
复制

4
1 1
a
b
5 5
aaaaa
abzba
10 13
dhhtyhwbsl
htahbsehtyhzb
7 2
contest
on

输出
复制

1
3
3
1

注意

在第一个测试用例中,您可以从字符串 $$$s$$$ 中取出子字符串 $$$«\mathtt{a}»$$$,将该字符串中的单个字母更改为 $$$«\mathtt{b}»$$$,并将其附加到字符串 $$$p$$$ 的末尾,从而使 $$$p$$$ 等于 $$$t$$$。

在第二个测试用例中,$$$t$$$可以通过$$$3$$$操作获得,如下所示:

$$«\mathtt{a\color{red}{b}}» + «\mathtt{\color{red}{z}}» + «\mathtt{\color{red}{b}a}»$$

修改的字符以红色突出显示。

在第三个测试用例中,可以通过如下方式获取字符串$$$t$$$:

$$«\mathtt{ht\color{red}{a}h}» + «\mathtt{bs\color{red}{e}}» + «\mathtt{htyh\color{red}{z}b}»$$