← 返回题目列表

Codeforces · 852/G

G. 浴室终端

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

史密斯在一间肮脏、废弃的浴室旁边醒来,他的脚踝被拴在管道上。他旁边是录音机,上面有手写的信息“播放我”。他在自己的后兜里发现了一盘磁带。将磁带放入录音机后,他看到天花板上挂着一把钥匙,钥匙被拴在某种机器上,该机器连接到他旁边的终端。按下“播放”按钮后,磁带上开始播放粗略的声音:

“听着史密斯。正如你所看到的,你的处境非常艰难,为了逃脱,你必须解决一个谜题。

给你 N 个代表单词的字符串。每个单词的最大长度为 L,由字符“a”-“e”组成。您还会获得代表模式的 M 个字符串。 Pattern 是长度 ≤ L 的字符串,由字符“a”-“e”以及最多 3 个字符“?”组成。字符“?”是一个未知字符,这意味着它可以等于任何字符“a”-“e”,甚至可以是空字符。对于每个模式,找到与给定模式匹配的单词数。解决该问题并在终端中输入结果后,钥匙将从天花板上掉落,您可能会逃脱。让比赛开始吧。”

帮助史密斯逃脱。

输入

输入的第一行包含两个整数N和M(1 ≤ N ≤ 100 000, 1 ≤ M ≤ 5000),分别代表单词和模式的数量。

接下来的 N 行代表每个单词,在这 N 行之后,接下来的 M 行代表每个模式。每个单词和每个模式都有最大长度 L (1 ≤ L ≤ 50)。每个模式的字符“?”不超过三个。单词和模式中的所有其他字符都是从“a”到“e”的小写英文字母。

输出

输出包含M行,每行由一个整数组成,表示与相应模式匹配的单词数。

示例

输入 #1

3 1
abc
aec
ac
a?c

输出 #1

3

注意

如果我们切换“?”对于“b”、“e”和空字符,我们分别得到“abc”、“aec”和“ac”。