Subset Equality

题目描述

奶牛们正在尝试一种新的方式来互相交换加密信息：她们会在相关字母之间混入无关字母，使消息更难被解码。 奶牛会传输两个字符串 $s$ 和 $t$，它们的长度均不超过 $10^5$，且只由小写英文字母 'a' 到 'r' 组成。为了尝试理解这段加密信息，你将得到 $Q$ 个查询（$1 \leq Q \leq 10^5$）。每个查询给出 'a' 到 'r' 之间小写字母的一个子集。你需要对每个查询判断：当 $s$ 和 $t$ 只保留查询中出现的字母（删除其他字母）后，二者是否相等。

输入格式

第一行包含 $s$。 第二行包含 $t$。 第三行包含 $Q$。 接下来的 $Q$ 行每行包含一个查询字符串。在一个查询字符串中，没有字母会重复出现。此外，所有查询字符串都按字典序排序，且不会有重复的查询字符串出现。

输出格式

对每个查询，如果将 $s$ 和 $t$ 仅保留查询中的字母后相等，则输出 'Y'，否则输出 'N'。

aabcd
caabd
4
a
ac
abd
abcd

YNYN

提示

对于第一个查询，当只保留 'a' 时，两个字符串都变为 "aa"。 对于第二个查询，第一个字符串变为 "aac"，而第二个字符串变为 "caa"。 评分： 测试点 2 满足 $|s|, |t|, Q \le 1000$。 测试点 3-11 没有额外限制。 题目来源：Danny Mittal

标签: USACO|2022|Silver

来源

USACO|2022|Silver