← 返回题目列表

Codeforces · 832/B

B. Petya 和考试

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

现在日子不好过。今天 Petya 需要在信息学考试中获得 100 分。这些任务对 Petya 来说似乎很简单,但他认为自己没有时间完成所有任务,所以他请你帮忙完成一项任务。

语句中存在 glob 模式(由小写英文字母、字符“?”和“*”组成的字符串)。已知字符“*”在模式中出现不超过一次。

此外,给定n个查询字符串,需要确定每个查询字符串的模式是否匹配。

一切对Petya来说似乎很简单,但随后他发现特殊图案字符与通常的含义不同。

如果可以替换每个字符“?”,则模式与字符串匹配。一个好的小写英文字母,以及字符“*”(如果有的话)与任何一串(包括空的)坏的小写英文字母,使得结果字符串与给定字符串相同。

好信都给了Petya。其他的都不好。

输入

第一行包含一个长度为 1 到 26 的字符串,由不同的小写英文字母组成。这些信都是好信,其他的都是坏信。

第二行包含模式 — 由小写英文字母组成的字符串 s,字符“?”和“*”(1 ≤ |s| ≤ 105)。保证字符“*”在 s 中出现不超过一次。

第三行包含整数 n (1 ≤ n ≤ 105) — 查询字符串的数量。

接下来有 ​​n 行,每行都包含由小写英文字母组成的单个非空字符串 - 查询字符串。

保证所有查询字符串的总长度不大于105。

输出

打印 n 行:如果模式与第 i 个查询字符串匹配,则在第 i 行中打印“YES”,否则打印“NO”。

您可以任意选择每个字母的大小写(小写或大写)。

示例

输入 #1

ab
a?a
2
aaa
aab

输出 #1

YES
NO

输入 #2

abc
a?a?a*
4
abacaba
abaca
apapa
aaaaax

输出 #2

NO
YES
NO
YES

注意

在第一个示例中,我们可以替换“?”好的字母“a”和“b”,所以我们可以看到第一个查询的答案是“YES”,第二个查询的答案是“NO”,因为我们无法匹配第三个字母。

第二个示例的说明。

- 第一个查询:“NO”,因为字符“*”只能替换为一串坏字母,但匹配查询字符串的唯一方法是将其替换为字符串“ba”,其中两个字母都是好字母。
- 第二个查询:“YES”,因为字符“?”可以替换为对应的好字母,字符“*”可以替换为空字符串,字符串会重合。
- 第三个查询:“NO”,因为字符“?”不能用坏字母代替。
- 第四个查询:“YES”,因为字符“?”可以用好字母“a”替换,而字符“*”可以用一串坏字母“x”替换。