| Submit | All submissions | Best solutions | Back to list |
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
| 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
|
||||||
|
2019-04-09 12:44:24
can solve it with hashing Last edit: 2019-04-09 12:46:11 |
||||||
|
2019-04-09 12:07:19
badihi |
||||||
|
2018-08-04 16:33:56
Not only Trie. Try other data structure or algorithm. Last edit: 2018-08-05 10:21:23 |
||||||
|
2017-12-12 13:42:42
You don't need bool isEndOfWord as there is no delete operation required, instead use a counter variable for each node to smoothly handle duplicates. While inserting, increment the counter variable, thus duplicates will be counted. |
||||||
|
2017-11-22 20:09:02
Good problem for data structure implementation... |
||||||
|
2017-10-19 19:17:32
@morass ... My submission in CPP14 times out (test 15) but in clang CPP it passes with 3.74 sec. Any idea why this might happen ? |
||||||
|
2017-09-20 15:43:46
My first problem using trie :) AC in 1 go |
||||||
|
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 |
||||||
RSS