Kotlin Heroes: Episode 7 |
---|
Finished |
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.
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$$$.
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.
2 1 a c 4 aa ca mm cf
1 2 0 1
6 3 dba abd cbb ada add bdd 5 ccbb abdd adba bada dddd
1 3 2 1 0
Explanation of the first test of the example:
Name |
---|