← 返回题目列表

Codeforces · 1898/E

E. 索菲亚和弦

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

Sofia 有一个长度为 $$$n$$$ 的字符串 $$$s$$$,仅由小写英文字母组成。她可以使用该字符串执行以下类型的操作。

1. 选择索引 $$$1 \le i \le |s|$$$ 并从字符串中删除字符 $$$s_i$$$。
2. 选择一对索引 $$$(l, r)$$$ ($$$1 \le l \le r \le |s|$$$) 并按字母顺序对子字符串 $$$s_{l} s_{l+1} \ldots s_r$$$ 进行排序。

Sofia 希望在如上所述对字符串 $$$s$$$ 执行零次或多次操作后获取长度为 $$$m$$$ 的字符串 $$$t$$$。请判断是否可以。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$、$$$m$$$ ($$$1\leq m \leq n \leq 2\cdot 10^5$$$) — 分别是字符串 $$$s$$$ 和 $$$t$$$ 的长度。

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

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

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,如果 Sofia 可以使用上述操作从 $$$s$$$ 获取字符串 $$$t$$$,则输出“YES”。否则,输出“NO”。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。

示例

输入 #1

8
5 5
sofia
afios
3 2
cba
bc
5 1
sofia
e
15 7
anavolimilovana
aamanan
26 4
abcdefghijklmnopqrstuvwxyz
nope
26 4
zyxwvutsrqponmlkjihgfedcba
nope
7 3
apricot
cat
3 3
cba
acb

输出 #1

YES
YES
NO
YES
NO
YES
NO
YES

注意

在第一个测试用例中,Sofia 可以执行以下操作:

1. $$$l=1$$$ 和 $$$r=5$$$ 的第二类运算:字符串 $$$s$$$ 之后变为 $$$\mathtt{afios}$$$。

在第二个测试用例中,Sofia 可以执行以下操作:

1. $$$l=1$$$ 和 $$$r=2$$$ 的第二种运算:字符串 $$$s$$$ 之后变为 $$$\mathtt{bca}$$$;
2. $$$i=3$$$ 的第一类运算:字符串$$$s$$$ 后面变成$$$\mathtt{bc}$$$。

在第三个测试用例中,可以证明使用提供的操作不可能从 $$$s$$$ 获得 $$$t$$$。