4455: Finding Words
内存限制：512 MB
时间限制：2 S
标准输入输出
题目类型：传统
评测方式：Special Judge
上传者：
提交：13
通过：0
题目描述
Bob is writing his thesis, and he wants to use some advanced vocabulary. Unfortunately, he has forgotten how to spell some of the words. He just remember some characters at the beginning and ending. Now he need your help to find all the possible words.
Bob will give you a query which consists of lowercase letters and one asterisk(*), The asterisk could be replaced by zero or more letters. You need to find all the words which match the query. For example, if the query is “a*nd”, then you may tell him the words “and”, “append”, “attend”, etc.
输入格式
There is only one test case. The first line contains the number of words n(1 ≤ n ≤ 105) in the dictionary. Each of the following n lines contains a word which consists of lowercase letters. The length of each word is not more than 30. The next line contains the number of queries q(1 ≤ q ≤ 105). Each of the following q lines contains a query which consists of zero or more lowercase letters and one asterisk. The length of each query is not more than 30.
输出格式
For each query, print the number of words in the dictionary which match the query.
输入样例 复制
4
and
abandon
append
island
3
ab*
*nd
a*nd输出样例 复制
1
3
2