← 返回题目列表

AtCoder · code_thanks_festival_2015_e

E. 噪声消除

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

問題文

您在某公司担任程序员。

在这家公司,您的工作是确定指定的字符串是否包含在从用户收集的某个字符串系列中。

例如,字符串 rhd 是一个字符串 表示 thisisrhdcontest ,但是字符串 thanks 或字符串 不包含在 ratheads 中。

然而,经过用户询问后发现,用户提交的字符串中存在不必要的字符,属于噪声,并且没有按照用户的要求进行判断。

所以你可以执行以下操作 Q 查询 我决定编写一个程序来处理 1 假设一直下雨,直到 Q 。

查询 i : 「文字列 S_i 和字符串 给出了 T_i 。一些字符 选择 x_1, x_2, ... , x_k (1 你甚至不必选择一个字符),字符串 通过从 S_i 中删除所有选定字符而获得的字符串 内部的字符串可以被视为 S'_i 确定是否可以包含 T_i 。”

例如, 来自S_1 = ratheads, T_1 = rhd 时,S_1 的角色 删除 a, e, t 后得到的字符串 S'_1 = rhds 是一个字符串 该字符串因为它包含 T_1 = rhd 可以包含 T_1 。


入力

输入是按以下格式从标准输入给出的。

Q
S_1 T_1
S_2 T_2
:
S_Q T_Q
  • 1 行显示查询数量。 Q (1 ≦ Q ≦ 5,000) 。 来自行
  • 2 从行 Q 行提供有关查询的信息。其中 i (1 ≦ i ≦ Q) 行仅由半角小写字母组成 2 字符串 跨 S_i, T_i (1 ≦ |S_i| ≦ 50, 1 ≦ |T_i| ≦ 50) 用空格分隔。

出力

Q 线输出。Q 行数过多 i (1 ≦ i ≦ Q) 行包含查询 打印 i 的答案。如果查询怎么办 i 中的字符串 如果可以包含 T_i 可以包括在内 YES ,否则 输出 NO 。还在输出末尾添加换行符。


入力例1

4
ratheads rhd
thisisrhdcontest rhd
yes no
abba aba

出力例1

YES
YES
NO
NO

查询是 4 有一个。

  • 查询 1 如问题文本中的示例所示。S_1 的角色 删除 a, e, t 后得到的字符串 S'_1 = rhds 是一个字符串 该字符串因为它包含 T_1 已包含在内,因此 输出YES 。
  • 查询 2 是一个字符串 未从 S_2 中删除字符的字符串 S_2 中的字符串 T_2 已包含在内,因此 输出 YES 。 无论您如何从
  • 查询 3 是一个字符串 未从 S_3 中删除字符,该字符串都会保留 S'_3 中的字符串 T_3 不包括在内,所以 NO 。 无论您如何从
  • 查询 4 是一个字符串 未从 S_4 中删除字符,该字符串都会保留 S'_4 中的字符串 T_4 不包括在内,所以 NO 。 无论您如何从

请注意,在指定字符并删除该字符时,不可能在不删除部分字符的情况下保留指定字符。


入力例2

5
abcdef bdf
aabbccdd b
abcabcabc aaba
abcdcba dba
ababababa aba

出力例2

YES
YES
NO
YES
YES