← 返回题目列表

Codeforces · 1278/A

A. 随机散列

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

Polycarp 建立了自己的网络服务。作为一种现代网络服务,它包含登录功能。这总是意味着密码安全问题。

Polycarp 决定存储由以下算法生成的密码哈希值:

1. 取密码$$$p$$$,由小写拉丁字母组成,将其中字母随机打乱,得到$$$p'$$$($$$p'$$$仍可等于$$$p$$$);
2. 生成两个随机字符串,由小写拉丁字母组成,$$$s_1$$$ 和 $$$s_2$$$(其中任何一个字符串都可以为空);
3. 生成的哈希 $$$h = s_1 + p' + s_2$$$,其中加法是字符串连接。

例如,让密码$$$p =$$$“abacaba”。那么 $$$p'$$$ 可以等于“aabcaab”。随机字符串 $$$s1 =$$$ "zyx" 和 $$$s2 =$$$ "kjh"。然后$$$h =$$$“zyxaabcaabkjh”。

请注意,$$$p$$$ 中不能删除或添加任何字母来获得 $$$p'$$$,只能更改顺序。

现在Polycarp要求你帮助他实现密码检查模块。给定密码 $$$p$$$ 和哈希值 $$$h$$$,检查 $$$h$$$ 是否可以是密码 $$$p$$$ 的哈希值。

你的程序应该回答 $$$t$$$ 独立测试用例。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。

每个测试用例的第一行包含一个非空字符串 $$$p$$$,由小写拉丁字母组成。 $$$p$$$ 的长度不超过$$$100$$$。

每个测试用例的第二行包含一个非空字符串 $$$h$$$,由小写拉丁字母组成。 $$$h$$$ 的长度不超过$$$100$$$。

输出

对于每个测试用例,打印答案 - 如果可以从给定密码 $$$p$$$ 获得给定哈希值 $$$h$$$,则打印“是”,否则打印“否”。

示例

输入 #1

5
abacaba
zyxaabcaabkjh
onetwothree
threetwoone
one
zzonneyy
one
none
twenty
ten

输出 #1

YES
YES
NO
YES
NO

注意

第一个测试用例在语句中进行了解释。

在第二个测试用例中,$$$s_1$$$ 和 $$$s_2$$$ 都是空的,并且 $$$p'=$$$ "thirdtwoone" 被 $$$p$$$ 打乱。

在第三个测试用例中,无法从密码中获取哈希值。

在第四个测试用例 $$$s_1=$$$ "n" 中,$$$s_2$$$ 为空,$$$p'=$$$ "one" 被 $$$p$$$ 洗牌(即使认为它保持不变)。

在第五个测试用例中,无法从密码中获取哈希值。