问题 J: 字典树again

问题 J: 字典树again

时间限制: 1 Sec  内存限制: 128 MB
提交: 264  解决: 55
[状态] [讨论版] [提交] [命题人:]
题目描述

Gy最近学习了字典树结构,无聊的他又想到了一个新的问题,给定一个字符串集合S={str1, str2, ,strn}和一个字符串str,在str后接尽量少的字符,使其属于S。当然如果str本身属于Sstr即为答案。

输入

第一行一个正整数T(T <= 10),表示有T组数据。

每组数据输入格式如下:

第一行为一个正整数N(0<N<20000),表示字符串集合内的字符串数。

接下来N行,每行一个字符串,表示集合中的串。

接下来一行是一个正整数Q(0<Q<200),表示有Q次询问。

接下来Q行,每行一个字符串str

所有字符串均由小写英文字母组成,且1<=长度<=20

输出

每组数据输出格式如下:

先输出“Case x:”,x表示是第几组数据,然后输出一个换行。

接下来输出Q行,对于每次询问,如果str能够添加字符使其属于字符串集合,则输出长度最小的(str添加字符后构成的串),有多个满足条件的话输出字典序最小的。否则输出-1

样例输入 Copy
3
3
abc
abd
aba
3
ab
ad
abc
2
bcde
bcdef
1
bcd
3
abc
def
hig
1
kkkk
样例输出 Copy
Case 1:
aba
-1
abc
Case 2:
bcde
Case 3:
-1