Shuffle Hashing

题意翻译

# 题目描述 Polycrap正在建立他自己的网页服务。作为一个很现代的网站其包含登入的功能。当然，这总会涉及到密码的安全问题。 Polycarp决定要储存密码的哈希值。密码的哈希值由以下这个算法来生成： 1.把只包含小写拉丁字母的密码$p$进行随机打乱，记为$p'$（$p'$可能和$p$相等）； 2.生成两个随机的只包含小写拉丁字母的字符串$s_1$和$s_2$（这两个串中的任何一个可能为空串）； 3.哈希算法的结果$h=s_1+p'+s_2$，此处的$+$是指把前后两个字符串首尾相接。 举个例子，$p=\texttt {abacaba}$，则$p'$可能为$\texttt{aabcaab}$。随机生成两个字符串$s_1=\texttt{zyx}",s_2=\texttt{kjh}$。那么$h=\texttt{zyxaabcaabkjh}$。 需要注意的是，从$p$变换道$p'$的过程中，不会添加或者删除任何字母，只会改变字母的顺序。 现在Polycarp想让你帮他编写密码哈希的校验模块。给出密码$p$和生成的哈希$h$，你需要检查$h$是否是$p$的一个哈希结果。 # 输入格式 第一行包含了一个正整数$t(1\leq t\leq100)$——查询的次数。 每一次查询的第一行包含了一个由小写拉丁字母组成的非空字符串$p$。$p$的长度不超过$100$。 每一次查询的第二行包含了一个由小写拉丁字母组成的非空字符串$h$。$h$的长度不超过$100$。 # 输出格式 对于每一次查询，如果$h$是$p$的一个哈希结果，就输出"YES"，反之输出"NO"。 # 说明/提示 第一组查询的解释已经在题干中给出。 第二组查询中$s_1$和$s_2$均是空串，$p'$是$p$的一种打乱。 第三组查询中哈希不能通过密码生成。 第四组查询中$s_1=\texttt{n}$，$s_2$是空串，$p'=\texttt{one}$是$p$的一种打乱（虽然打乱并没有效果）。 第五组查询中哈希不能通过密码生成。

题目描述

Polycarp has built his own web service. Being a modern web service it includes login feature. And that always implies password security problems. Polycarp decided to store the hash of the password, generated by the following algorithm: 1. take the password $ p $ , consisting of lowercase Latin letters, and shuffle the letters randomly in it to obtain $ p' $ ( $ p' $ can still be equal to $ p $ ); 2. generate two random strings, consisting of lowercase Latin letters, $ s_1 $ and $ s_2 $ (any of these strings can be empty); 3. the resulting hash $ h = s_1 + p' + s_2 $ , where addition is string concatenation. For example, let the password $ p = $ "abacaba". Then $ p' $ can be equal to "aabcaab". Random strings $ s1 = $ "zyx" and $ s2 = $ "kjh". Then $ h = $ "zyxaabcaabkjh". Note that no letters could be deleted or added to $ p $ to obtain $ p' $ , only the order could be changed. Now Polycarp asks you to help him to implement the password check module. Given the password $ p $ and the hash $ h $ , check that $ h $ can be the hash for the password $ p $ . Your program should answer $ t $ independent test cases.

输入输出格式

输入格式

The first line contains one integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. The first line of each test case contains a non-empty string $ p $ , consisting of lowercase Latin letters. The length of $ p $ does not exceed $ 100 $ . The second line of each test case contains a non-empty string $ h $ , consisting of lowercase Latin letters. The length of $ h $ does not exceed $ 100 $ .

输出格式

For each test case print the answer to it — "YES" if the given hash $ h $ could be obtained from the given password $ p $ or "NO" otherwise.

输入输出样例

输入样例 #1

5
abacaba
zyxaabcaabkjh
onetwothree
threetwoone
one
zzonneyy
one
none
twenty
ten

输出样例 #1

YES
YES
NO
YES
NO

说明

The first test case is explained in the statement. In the second test case both $ s_1 $ and $ s_2 $ are empty and $ p'= $ "threetwoone" is $ p $ shuffled. In the third test case the hash could not be obtained from the password. In the fourth test case $ s_1= $ "n", $ s_2 $ is empty and $ p'= $ "one" is $ p $ shuffled (even thought it stayed the same). In the fifth test case the hash could not be obtained from the password.