描述

“搜索引擎”这个词对你来说可能并不陌生。一般来说，搜索引擎会在互联网上搜索可用的网页，提取并组织信息，并用最相关的页面回应用户的查询。像GOOGLE这样的世界著名的搜索引擎，已经成为我们在网上浏览时使用的重要工具。如今，以下对话在我们的日常生活中已经非常常见：

“****** 这个词是什么意思？”
“嗯……我不太确定，去谷歌搜一下吧。”

在这个问题中，你需要构建一个小型搜索引擎。听起来不可能，对吧？别担心，这里有一个教程，一步步教你如何高效地组织大量文本并快速响应查询。你不需要担心网页的抓取过程，所有网页都以文本格式作为输入数据提供给你。此外，还提供了许多查询来验证你的系统。

现代搜索引擎使用一种称为“倒排”的技术来处理非常大的文档集合。这种方法依赖于构建一个称为“倒排索引”的数据结构，它将术语（单词）与它们在文档集合中的出现位置相关联。感兴趣的术语集合称为词汇表，记作 $V$。在其最简单的形式中，倒排索引是一个字典，其中每个搜索键是一个术语 $\omega \in V$。与之相关联的值 $b(\omega)$ 是指向一个额外的中间数据结构——称为“桶”的指针。与某个术语 $\omega$ 相关联的桶本质上是一个标记 $\omega$ 在文本集合中所有出现位置的指针列表。每个桶中的每个条目仅由文档标识符（DID）、文档在集合中的序号以及术语在文档中的出现行号组成。

我们以图1为例，它描述了整体结构。假设我们只有三份文件需要处理，如图1右侧所示；首先我们需要对文本进行分词（使用空格、标点符号和其他非字母字符分隔单词），并从文档中出现的术语构建我们的词汇表。为了简化问题，我们不需要考虑任何短语，只需要将单个单词作为术语。此外，术语不区分大小写（例如，我们认为“book”和“Book”是相同的术语），我们也不考虑任何形态变体（例如，我们认为“books”和“book”、“protected”和“protect”是不同的术语），以及带连字符的单词（例如，“middle-class”不是一个单独的术语，而是通过连字符分成两个术语“middle”和“class”）。词汇表如图1左侧所示。词汇表中的每个术语都有一个指向其桶的指针。桶的集合如图1中间部分所示。桶中的每个条目记录了术语出现的DID。

在构建了整个倒排索引结构之后，我们可以将其应用于查询。查询的格式如下：

• 单个术语
• 术语 AND 术语
• 术语 OR 术语
• NOT 术语

单个术语可以通过布尔运算符（AND、OR 和 NOT）组合起来：“term1 AND term2”表示查询包含term1和term2的文档；“term1 OR term2”表示查询包含term1或term2的文档；“NOT term1”表示查询不包含term1的文档。术语是如上定义的单个单词。你可以保证术语中不会出现任何非字母字符，并且所有术语都是小写的。此外，在我们的问题中，一些无意义的停用词（如冠词、介词和副词，具体为“the, a, to, and, or, not”）也不会出现在查询中。

对于每个查询，基于构建的倒排索引的引擎会在词汇表中搜索术语，比较术语的桶信息，然后将结果呈现给用户。现在你能构建这个引擎吗？

输入

输入以一个整数 $N$（$0 < N < 100$）开始，表示提供的 $N$ 份文档。接下来的 $N$ 个部分是 $N$ 份文档。每个部分包含文档内容，并以一行十个星号结束。

你可以假设每行不超过80个字符，$N$ 份文档的总行数不超过1500行。

接下来，给出一个整数 $M$（$0 < M \leq 50000$），表示查询的数量，随后是 $M$ 行，每行一个查询。所有查询都符合上述描述的格式。

输出

对于每个查询，你需要找到满足查询的文档，并且只输出包含搜索术语的文档行（对于 NOT 查询，你需要输出整个文档）。你应该按照输入中出现的顺序打印行。用一行10个破折号分隔不同的文档。

如果没有找到匹配查询的文档，只需输出一行：“Sorry, I found nothing.”

每个查询的输出以一行10个等号结束。

==========

输入数据 1

4  
A manufacturer, importer, or seller of  
digital media devices may not (1) sell,  
or offer for sale, in interstate commerce,  
or (2) cause to be transported in, or in a  
manner affecting, interstate commerce,  
a digital media device unless the device  
includes and utilizes standard security  
technologies that adhere to the security  
system standards.  
**********  
Of course, Lisa did not necessarily  
intend to read his books. She might  
want the computer only to write her  
midterm. But Dan knew she came from  
a middle-class family and could hardly  
afford the tuition, let alone her reading  
fees. Books might be the only way she  
could graduate  
**********  
Research in analysis (i.e., the evaluation  
of the strengths and weaknesses of  
computer system) is essential to the  
development of effective security, both  
for works protected by copyright law  
and for information in general. Such  
research can progress only through the  
open publication and exchange of  
complete scientific results  
**********  
I am very very very happy!  
What about you?  
**********  
6  
computer  
books AND computer  
books OR protected  
NOT security  
very  
slick

输出数据 1

want the computer only to write her  
----------  
computer system) is essential to the  
==========  
intend to read his books. She might  
want the computer only to write her  
fees. Books might be the only way she  
==========  
intend to read his books. She might  
fees. Books might be the only way she  
----------  
for works protected by copyright law  
==========  
Of course, Lisa did not necessarily  
intend to read his books. She might  
want the computer only to write her  
midterm. But Dan knew she came from  
a middle-class family and could hardly  
afford the tuition, let alone her reading  
fees. Books might be the only way she  
could graduate  
----------  
I am very very very happy!  
What about you?  
==========  
I am very very very happy!  
==========  
Sorry, I found nothing.  
==========

来源

北京2004