Bathroom terminal

题意翻译

给你 $N$ 个字符串，它们代表了单词。每个单词只由字符 `'a'-'e'` 组成，最大长度为 $L$ 。另外，有 $M$ 个模式串，由字符 `'a'-'e'` 和至多三个的 '?' 组成，最大长度为 $L$ 。其中， '?' 可以代表 `'a'-'e'` 中的任何一个字符以及一个空字符 `''` 。对于每一个模式串，输出与之匹配的单词数。 输入格式： 第一行是两个整数 $N$ 和 $M$ 。 接下来的 $N$ 行是 $N$ 个单词。 接下来的 $M$ 行是 $M$ 个模式串。 输出格式： 对于每一个模式串，输出与之匹配的单词的个数。 样例说明： 与 `'a?e'` 匹配的单词有 `'abc'` 、 `'aec'` 和 `'ac'`。 translated by @callG

题目描述

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.

输入输出格式

输入格式

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'.

输出格式

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

输入输出样例

输入样例 #1

3 1
abc
aec
ac
a?c

输出样例 #1

3

说明

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