DICT - Search in the dictionary!

no tags 

    Eloy the byte is helping his son, Marcos the little one, with the homework, which consists on: Given one or more words you should search in the dictionary which word contains the proper prefix of the word given, for example
    set is a prefix of setter, but also of setting.
    Now, neither Eloy nor Marcos wants to search the words in the dictionary (they just won’t do it)… Marcos will give you the words in the dictionary and the words to find the prefix of… You should make a program that given this, output the list of words that contains as a prefix the word given, Marcos can make mistakes sometimes, so, be careful! Marcos won’t always be telling the real prefixes all the time, in addition, sometimes Marcos can repeat the same word (while reading the dictionary), in this case, the word should be treated as it was mentioned just one time.

    INPUT:
    The input will consist in an integer N (1<=N<=25.000), next, N lines will follow containing a single word (maximum of 20 characters (all lowercase letters)), after that, there will be an integer K (1<=K<=22.000) containing the number of words to look in the dictionary, then, K lines containing the prefix-word.

    OUTPUT:
    The output will consist in displaying the words that are composed from the word given, you should output “Case #i:” where i is the i-th case, then, at the next line, output the list of the composed words (lexicographical-ordered), if there is none, you should output “No match.”

SAMPLE DATA:

INPUT:

5

set

lol

setter

setting

settings

2

set

happy

OUTPUT:

Case #1:

setter

setting

settings

Case #2:

No match.


hide comments
aliosm: 2017-03-14 19:00:01

AC with cin, cout, string C++14 :3

kshubham02: 2017-01-17 12:24:02

@poda_venna it means that a test case like this is possible-
12
bittorrent
bit
bittorrent
bittu
bansi
bansi
bikaner
bhalu
bhokal
chammach
chamakh
claire
2
bit
cham

PS(General): Do not use cin, cout or std::string. Resort to scanf, printf and char*.

Last edit: 2017-01-17 12:31:57
apar03: 2016-10-15 22:58:16

Weak test cases

razor123: 2016-09-05 21:45:09

Use char array ,scanf,printf to pass the test cases even sync_with_stdio(false) doesn't work

poda_venna: 2016-09-03 20:48:03

sometimes Marcos can repeat the same word (while reading the dictionary), in this case, the word should be treated as it was mentioned just one time

what does this mean??

galang: 2016-08-16 02:22:21

u dont need scanf printf and c char arrays...
i used cin, cout and got ac 0.48 s... :/ (but i use ios_base::sync_with_stdio(false) and cin.tie(0)

Shubham Pandey: 2016-06-24 20:06:45

AC in 1st go ......and there is no need for compressed trie or ternary tree , trivial trie implementation would do

Last edit: 2016-06-27 20:29:53
noob909: 2016-06-20 13:02:26

2nd trie :D, use scanf and printf to avoid tle :)

cosmopoliton: 2016-05-31 10:01:41

use printf and scanf and also try create trie dynamically as i used array of structure i got a lot of tle :) .but at last i trie(d) the question :P.

naruto09: 2016-05-17 15:14:29

finally AC...!! Trie(d) very hard for this one..:P


Added by:david_8k
Date:2012-01-12
Time limit:0.148s-0.445s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem