A1314. [COCI-2015_2016-contest5]#2 OOP
编程题
普及/提高-
知识点
题目描述
Little Matej is solving an OOP (Object-oriented programming) laboratory exercise and he’s having trouble with solving one subtask.
He is given a set that contains N words. He is also given Q queries where each query is one pattern. A pattern consists of a single character “*” and lowercase letters of the English alphabet. For example, “*”, “kul*to”, “ana*”.
A pattern is said to cover a word if such an array of letters (which can be empty) exists that, when replacing the character ‘*’, the pattern and the word become completely identical. It is necessary to output how many words each pattern covers.
I
He is given a set that contains N words. He is also given Q queries where each query is one pattern. A pattern consists of a single character “*” and lowercase letters of the English alphabet. For example, “*”, “kul*to”, “ana*”.
A pattern is said to cover a word if such an array of letters (which can be empty) exists that, when replacing the character ‘*’, the pattern and the word become completely identical. It is necessary to output how many words each pattern covers.
I
输入格式
The first line of input contains two integers N and Q (1 6 N, Q 6 100 000).
Each of the following N lines contains a word that consists of lowercase letters of the English alphabet.
Each of the following Q lines contains a pattern for which you need to output how many words from the first set it covers.
The total number of characters will be less than 3 000 00
0.
Each of the following N lines contains a word that consists of lowercase letters of the English alphabet.
Each of the following Q lines contains a pattern for which you need to output how many words from the first set it covers.
The total number of characters will be less than 3 000 00
0.
输出格式
Output Q lines, the k th line containing the number of words that the k th pattern covers.
输入输出样例
输入 #1
3 3 aaa abc aba a*a aaa* *aaa
输出 #1
2 1 1
输入 #2
5 3 eedecc ebdecb eaba ebcddc eb e* *dca e*c
输出 #2
5 0 2
说明/提示
In test cases worth 40% of total points, it will additionally hold 1 6 N, Q 6 1000.