SPOJ.com - Problem ADAINDEX

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 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!

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

hide comments

2017-05-11 11:26:58
@morass i got your point . I will definitely try to make my solution better .

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

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

2017-04-08 21:15:37
AC IN ONE GO :)

2017-02-15 16:34:48 hacker_sk
AC 46th :)

Last edit: 2017-02-15 18:04:39

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!

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.

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!

2016-09-27 11:01:56 Bhumit
@morass

Can you please check my submission 17794751?
It's giving NZEC :/

2016-09-27 06:27:10 prakash
very easy trie.