SPOJ.com - Problem ADAINDEX

ADAINDEX - Ada and Indexing

#trie-1

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 10⁶

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

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

Submit solution!

hide comments

< Previous 1 2 3 4 Next >

	vivace: 2017-05-11 11:26:58 @morass i got your point . I will definitely try to make my solution better .
	morass: 2017-05-11 09:19:29 @vivace: Good day to you. Firstly, it can be written more "static" Secondly, the trie can be represented in other ways than you did (more sparse - for example linked-list like) GL ~/Morass
	vivace: 2017-05-10 20:23:51 Just got AC in 2.95 seconds with 242 mb memory. But fastest solution has 0.32 seconds time with 22 mb memory. How ?? @morass
	anurag_tangri: 2017-04-08 21:15:37 AC IN ONE GO :)
	hacker_sk: 2017-02-15 16:34:48 AC 46th :) Last edit: 2017-02-15 18:04:39
	morass: 2016-11-04 00:39:38 @d_pawan_kumar: Good day to you. There are several (more) things, yet the cause of compile-error is: A) The struct can't be declared like that in "main" B) You can't declare 10^5*10^5 array (as seen in the structure) So these are for the compile error {I guess you can take look at "errors" if you click on the "Compile Error"} Good Luck & Have nice day!
	d_pawan_kumar: 2016-11-03 07:58:33 @morass Can you please check my submission 18089898. My code is running perfectly on my pc but its showing compilation error over here.
	morass: 2016-09-27 12:50:55 @Bhumit: Good day to you, it ended with Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 64 at ADAINDEX$Reader.readLine(ADAINDEX.java:54) at ADAINDEX.main(ADAINDEX.java:215) Hope this will be enough ;-) Good Luck!
	Bhumit: 2016-09-27 11:01:56 @morass Can you please check my submission 17794751? It's giving NZEC :/
	prakash: 2016-09-27 06:27:10 very easy trie.

Submit solution!

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