ADAINDEX - Ada and Indexing


Ada the Ladybug has many things to do and almost no time. She wants to to save time while searching for something so she have decided to make a search engine.

She has many words in her TODO list. It costs her precious time to find out, whether a word is in it so she seeks your help. You will get list and some queries. You will be asked, to find out how many words in TODO list have a word as prefix.

Input

The first line contains N, Q: the number words in TODO list and number of queries.

N lines follow, with words (of TODO list) consisting of lowercase letters. The sum of their lengths won't be greater than 106

Q lines follow, with words (queries) consisting of lowercase letters. The sum of their lengths won't be greater than 106

Output

For each query print the number of words in TODO list which have actual word as prefix.

Example Input

12 6
bulldog
dog
dogged
doggedly
doggerel
dogma
dogmatic
dogmatism
dogs
catastroph
catastroph
doctor
cat
dog
dogg
do
doctrinography
dogge

Example Output

2
8
3
9
0
3

hide comments
f_rank_coder1: 2024-09-16 07:33:46

Can someone tell me what is wrong in my code? <snip>
[Simes]: try this test case:
3 3
a
aa
aaa
a
aa
aaa

Last edit: 2024-09-16 15:09:39
hoangptch: 2024-05-06 13:36:11

good

Last edit: 2024-05-06 13:37:04
mostafasazid: 2023-04-16 12:04:20

using trie data structure solved this

vineetjai: 2022-05-15 09:48:31

@Morass can you please check my hash solution is getting WA at Master Judge (Testcase 15)?

adiantek: 2021-01-28 00:47:15

How many lines (N, Q) and how long strings are?

sandeepd: 2020-01-15 23:11:07

Nice problem, thanks @Morass!

sajalagrawal14: 2019-10-16 18:34:11

good implementation of trie
<snip>

Last edit: 2022-11-14 12:44:56
vaishcr7: 2019-07-11 20:35:08

@morass . Can you tell me the issue with y submission 24137100, the same way as you helped bhumit.

Last edit: 2019-07-26 08:59:39
raftar2097: 2019-04-20 21:30:14

@cardinalx i tried using hash but got tle

Last edit: 2019-04-20 21:30:28
ameernsr: 2019-04-09 12:45:33

right!
@cardinalx


Added by:Morass
Date:2016-09-06
Time limit:6s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU