CF852G.Bathroom terminal

Smith wakes up at the side of a dirty, disused bathroom, his ankle chained to pipes. Next to him is tape-player with a hand-written message "Play Me". He finds a tape in his own back pocket. After putting the tape in the tape-player, he sees a key hanging from a ceiling, chained to some kind of a machine, which is connected to the terminal next to him. After pressing a Play button a rough voice starts playing from the tape:

"Listen up Smith. As you can see, you are in pretty tough situation and in order to escape, you have to solve a puzzle.

You are given N strings which represent words. Each word is of the maximum length L and consists of characters 'a'-'e'. You are also given M strings which represent patterns. Pattern is a string of length  ≤  L and consists of characters 'a'-'e' as well as the maximum 3 characters '?'. Character '?' is an unknown character, meaning it can be equal to any character 'a'-'e', or even an empty character. For each pattern find the number of words that matches with the given pattern. After solving it and typing the result in the terminal, the key will drop from the ceiling and you may escape. Let the game begin."

Help Smith escape.

史密斯在一间肮脏且废弃的浴室旁醒来，脚踝被铁链锁在管道上。他身旁放着一台录音机，上面有一张手写的字条：“播放我”。他在自己后裤兜里发现了一盘磁带。将磁带插入录音机后，他看到一把钥匙悬挂在天花板上，由一条铁链连接至某种机器，而该机器又与他身旁的一台终端相连。按下“播放”按钮后，录音机中传出一阵粗粝的声音：

“听着，史密斯。如你所见，你目前处境相当艰难；要想逃脱，你必须解开一道谜题。

你将获得 N 个字符串，每个字符串代表一个单词。每个单词的最大长度为 L，且仅由字符 'a'–'e' 组成。此外，你还获得 M 个字符串，每个字符串代表一个模式（pattern）。每个模式的长度 ≤ L，同样仅由字符 'a'–'e' 组成，且最多包含 3 个字符 '?'。字符 '?' 表示未知字符，它可以匹配任意一个字符 'a'–'e'，甚至可以匹配空字符（即该 '?' 可以被忽略，不匹配任何字符）。对于每个模式，请计算它能匹配多少个单词。解出答案后，将结果输入终端，钥匙便会从天花板上落下，你便可成功逃脱。游戏开始吧。”

请帮助史密斯逃脱。

The first line of input contains two integers N and M (1 ≤ N ≤  100 000, 1 ≤ M ≤  5000), representing the number of words and patterns respectively.

The next N lines represent each word, and after those N lines, following M lines represent each pattern. Each word and each pattern has a maximum length L (1 ≤ L ≤ 50). Each pattern has no more that three characters '?'. All other characters in words and patters are lowercase English letters from 'a' to 'e'.

输入的第一行包含两个整数 $N$ 和 $M$（$1 \leq N \leq 100\,000$，$1 \leq M \leq 5000$），分别表示单词的数量和模式的数量。

接下来的 $N$ 行每行表示一个单词；在这 $N$ 行之后，再接下来的 $M$ 行每行表示一个模式。每个单词和每个模式的最大长度为 $L$（$1 \leq L \leq 50$）。每个模式中最多包含三个字符 ?。单词和模式中的其余所有字符均为小写英文字母，且仅限于 'a' 到 'e'。

Output contains M lines and each line consists of one integer, representing the number of words that match the corresponding pattern.

输出包含 M 行，每行一个整数，表示匹配对应模式的单词数量。

If we switch '?' with 'b', 'e' and with empty character, we get 'abc', 'aec' and 'ac' respectively.

如果我们分别将 '?' 替换为 'b'、'e' 和空字符，我们得到的字符串分别为 'abc'、'aec' 和 'ac'。