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

Input:
5
set
lol
setter
setting
settings
2
set
happy

Output:
Case #1:
setter
setting
settings
Case #2:
No match.

hide comments
fuadul_hasan: 2021-05-04 13:59:56

simple (trie + dfs)..... nice problem

sarkybastard: 2020-09-24 23:38:31

yes. learn how spoj works. wrong test case somewhere might not be 5

viditbhardwaj: 2020-09-10 13:00:28

wrong TC 5...any idea.??

nihad_nabelsi: 2019-08-26 14:27:12

don't use scanf & printf with ios::sync.
that cost me many WA :(

sagar_june97p: 2019-05-30 11:05:36

Can be done via cin, cout, string class. Use fast IO to avoid TLE.

fahimsifnatul: 2018-11-01 14:29:18

trie + dfs ........ 0.18s ..AC in one go ^_^

flyingduchman_: 2018-04-18 15:14:18

Too strict time limit for Java

Last edit: 2018-04-18 15:15:10
avik26091998: 2018-01-13 15:10:52

Nice Trie poblem...

pranto_84: 2017-11-03 20:34:45

got WA :( :( :(
give some test case pls...

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

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


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