当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

3098:Frugal Search

题目描述

For this problem you will write a search engine that takes a query, searches a collection of words, and finds the lexicographically smallest word that matches the query (i.e., the matching word that would appear first in an English dictionary). A query is a sequence of one or more terms separated by single vertical bars ("|"). A term is one or more letters followed by zero or more signed letters. A signed letter is either +s ("positive" s) or -s ("negative" s), where s is a single letter. All letters are lowercase, and no letter will appear more than once within a term. A query will not contain spaces. A term matches a word if the word contains at least one of the unsigned letters, all of the positive letters, and none of the negative letters; a query matches a word if at least one of its terms matches the word.

输入解释

The input consists of one or more test cases followed by a line containing only "#" that signals the end of the input. Each test case consists of 1–100 words, each on a line by itself, followed by a line containing only "*" that marks the end of the word list, followed by one or more queries, each on a line by itself, followed by a line containing only "**" that marks the end of the test case. Each word will consist of 1–20 lowercase letters. All words within a test case will be unique. Each query will be as defined above and will be 1–79 characters long.

输出解释

For each query, output a single line containing the lexicographically smallest word within that test case that matches the query, or the word NONE if there is no matching word. At the end of each test case, output a dollar sign on a line by itself.

输入样例
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
**
#
输出样例
bat
NONE
elk
$
gentoo
ubuntu
NONE
$

该题目是Virtual Judge题目,来自 北京大学POJ

题目来源 Mid-Central USA 2006

源链接: POJ-3098

最后修改于 2020-10-29T06:52:31+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
1000 65536