A16708 | $Fuzzy Concatenation (Easy Version)$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

这是该问题的简易版本。不同之处在于本题中 $n \le 10^5, m \le 10^4$。只有在解决了所有版本后才能进行 hack。 现在有两个字符串 $s$ 和 $t$，它们均由小写拉丁字母组成。同时你还有一个初始为空的字符串 $p$。 你可以执行如下操作，每次操作包含若干阶段： - 任意选择两个整数 $l$ 和 $r$，满足 $1 \le l \le r \le |s|$； - 复制子串 $s_l,\ldots, s_r$，并将其追加到字符串 $p$ 的末尾； - 在 $p$ 最后新添加的 $r-l+1$ 个字符中，最多可以将其中任意一个字符修改为任意一个小写拉丁字母。 例如，若字符串 $s = $ "dhhtyhwbsl"，$p = $ ""，你可以选择 $l = 3, r = 6$，将 "htyh" 添加到 $p$ 的末尾，并把字符 "y" 改成 "a"，结果 $p = $ "htah"。 你的任务是，判断让字符串 $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$。

每组测试用例输出一个整数，表示答案。

输入 #1

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

输出 #1

C++ 编辑器

输入

输出