#P3098. Frugal Search
Frugal Search
描述
对于这个问题,您将编写一个搜索引擎,该引擎接受查询,搜索单词集合,并找到与查询匹配的字典顺序上最小的单词(即,在英语词典中首先出现的匹配单词)。查询是由单个竖线 (“|”) 分隔的一个或多个术语的序列。术语是一个或多个字母,后跟零个或多个签名字母。签名字母是 + (“positive” ) 或 - (“negative” ),其中 是单个字母。所有字母都是小写的,并且一个词中没有一个字母会出现多次。查询将不包含空格。如果单词包含至少一个无符号字母、所有正字母,并且不包含任何负字母,则术语与单词匹配;如果查询中至少有一个词与单词匹配,则查询与该单词匹配。
输入
输入由一个或多个测试用例组成,后跟仅包含“#”的行,该行表示输入结束。每个测试用例由 1-100 个单词组成,每个单词单独位于一行中,后跟一行仅包含“*”的行,用于标记单词列表的结尾,后跟一个或多个查询,每个查询单独位于一行上,后跟一行仅包含“**”的行,用于标记测试用例的结尾。每个单词将由 1-20 个小写字母组成。测试用例中的所有单词都将是唯一的。每个查询将如上所述,长度为 1-79 个字符。
输出
对于每个查询,输出一行,其中包含该测试用例中与查询匹配的字典顺序上最小的单词,如果没有匹配的单词,则输出单词 NONE。在每个测试用例的末尾,单独在一行上输出一个美元符号。
输入数据 1
elk
cow
bat
*
ea
acm+e
nm+o|jk+l
**
debian
slackware
gentoo
ubuntu
suse
fedora
mepis
*
yts
cab-e+n
r-e|zjq|i+t|vs-p+e-u-c
**
#
输出数据 1
bat
NONE
elk
$
gentoo
ubuntu
NONE
$