← 返回题目列表

Codeforces · 1451/C

C. 字符串相等

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

Ashish 有两个字符串 $$$a$$$ 和 $$$b$$$,每个字符串的长度为 $$$n$$$,以及一个整数 $$$k$$$。字符串仅包含小写英文字母。

他想通过对 $$$a$$$ 执行一些(可能为零)操作,将字符串 $$$a$$$ 转换为字符串 $$$b$$$。

只需一招,他就可以

- 选择索引 $$$i$$$ ($$$1 \leq i\leq n-1$$$) 并交换 $$$a_i$$$ 和 $$$a_{i+1}$$$,或者
- 选择索引 $$$i$$$ ($$$1 \leq i \leq n-k+1$$$) 并且如果 $$$a_i, a_{i+1}, \ldots, a_{i+k-1}$$$ 都等于某个字符 $$$c$$$ ($$$c \neq$$$ 'z'),则将每个字符替换为下一个字符$$$(c+1)$$$,即'a'被'b'替换,'b'被'c'替换,依此类推。

注意,他可以执行任意数量的操作,并且操作只能对字符串$$$a$$$进行。

帮助 Ashish 确定在对字符串 $$$a$$$ 执行一些(可能为零)操作后是否可以将其转换为 $$$b$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。每个测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ ($$$2 \leq n \leq 10^6$$$) 和 $$$k$$$ ($$$1 \leq k \leq n$$$)。

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

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

保证所有测试用例中$$$n$$$的值之和不超过$$$10^6$$$。

输出

对于每个测试用例,如果 Ashish 在一些动作后可以将 $$$a$$$ 转换为 $$$b$$$,则打印“Yes”,否则打印“No”。

您可以以任何大小写形式打印答案的字母(大写或小写)。

示例

输入 #1

4
3 3
abc
bcd
4 2
abba
azza
2 1
zz
aa
6 2
aaabba
ddddcc

输出 #1

No
Yes
No
Yes

注意

在第一个测试用例中,可以表明不可能将 $$$a$$$ 转换为 $$$b$$$。

在第二个测试用例中,

“阿巴”$$$\xrightarrow{\text{inc}}$$$“acca”$$$\xrightarrow{\text{inc}}$$$$$$\ldots$$$$$$\xrightarrow{\text{inc}}$$$“阿扎”。

这里“swap”表示第一类型的操作,并且“inc”表示第二类型的操作。

在第四个测试用例中,

“aaabba”$$$\xrightarrow{\text{swap}}$$$“aaabab”$$$\xrightarrow{\text{swap}}$$$“aaaabb”$$$\xrightarrow{\text{inc}}$$$$$$\ldots$$$$$$\xrightarrow{\text{inc}}$$$“ddaabb” $$$\xrightarrow{\text{inc}}$$$ $$$\ldots$$$ $$$\xrightarrow{\text{inc}}$$$ “ddddbb” $$$\xrightarrow{\text{inc}}$$$ $$$\ldots$$$ $$$\xrightarrow{\text{inc}}$$$ “ddddcc”。