Preparando MOJI

String Searching

3000ms 262144K

Description:

You are given an array $$$s$$$ consisting of $$$n$$$ different strings. Each string consists of $$$m$$$ lowercase Latin letters.

You have to respond to $$$q$$$ queries. Each query contains a string $$$t$$$ of length $$$m+1$$$. Count the number of indices $$$i$$$, such that the string $$$t$$$ can be obtained from the string $$$s_i$$$, if it is allowed to insert one letter in an arbitrary position.

Input:

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^5$$$; $$$1 \le m \le 10$$$) — the number of strings in the array and the length of each string.

The following $$$n$$$ lines contain strings $$$s_i$$$. All of the given strings are different.

The next line contains a single integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — the number of queries.

The following $$$q$$$ lines contain query strings $$$t$$$ of length $$$m + 1$$$.

Output:

For each query, print the number of indices $$$i$$$, such that a string from the query can be obtained from the string $$$s_i$$$, if it is allowed to insert one letter in an arbitrary position.

Sample Input:

2 1
a
c
4
aa
ca
mm
cf

Sample Output:

1
2
0
1

Sample Input:

6 3
dba
abd
cbb
ada
add
bdd
5
ccbb
abdd
adba
bada
dddd

Sample Output:

1
3
2
1
0

Note:

Explanation of the first test of the example:

  • the string a can be transformed into aa by inserting one letter;
  • both strings a and c can be transformed into ca by inserting one letter;
  • neither a nor c can be transformed into mm by inserting one letter;
  • c can be transformed into cf by inserting one letter.

Informação

Codeforces

Provedor Codeforces

Código CF1533D

Tags

*specialhashing

Submetido 0

BOUA! 0

Taxa de BOUA's 0%

Datas 09/05/2023 10:14:46

Relacionados

Nada ainda