The word "search engine" may not be strange to you. Generally speaking, a search engine searches the web pages available in the Internet, extracts and organizes the information and responds to users' queries with the most relevant pages. World famous search engines, like GOOGLE, have become very important tools for us to use when we visit the web. Such conversations are now common in our daily life:
"What does the word like ∗ ∗ ∗ ∗ ∗∗ mean?" "Um. . . I am not sure, just google it."
In this problem, you are required to construct a small search engine. Sounds impossible, does it? Don't worry, here is a tutorial teaching you how to organize large collection of texts efficiently and respond to queries quickly step by step. You don't need to worry about the fetching process of web pages, all the web pages are provided to you in text format as the input data. Besides, a lot of queries are also provided to validate your system.
Modern search engines use a technique called inversion for dealing with very large sets of documents. The method relies on the construction of a data structure, called an inverted index, which associates terms (words) to their occurrences in the collection of documents. The set of terms of interest is called the vocabulary, denoted as V . In its simplest form, an inverted index is a dictionary where each search key is a term ω ∈ V . The associated value b(ω) is a pointer to an additional intermediate data structure, called a bucket. The bucket associated with a certain term ω is essentially a list of pointers marking all the occurrences of ω in the text collection. Each entry in each bucket simply consists of the document identifier (DID), the ordinal number of the document within the collection and the ordinal line number of the term's occurrence within the document.
Let's take Figure-1 for an example, which describes the general structure. Assuming that we only have three documents to handle, shown at the right part in Figure-1; first we need to tokenize the text for words (blank, punctuations and other non-alphabetic characters are used to separate words) and construct our vocabulary from terms occurring in the documents. For simplicity, we don't need to consider any phrases, only a single word as a term. Furthermore, the terms are case-insensitive (e.g. we consider "book" and "Book" to be the same term) and we don't consider any morphological variants (e.g. we consider "books" and "book", "protected" and "protect" to be different terms) and hyphenated words (e.g. "middle-class" is not a single term, but separated into 2 terms "middle" and "class" by the hyphen). The vocabulary is shown at the left part in Figure-1. Each term of the vocabulary has a pointer to its bucket. The collection of the buckets is shown at the middle part in Figure-1. Each item in a bucket records the DID of the term's occurrence.
After constructing the whole inverted index structure, we may apply it to the queries. The query is in any of the following formats:
term term AND term term OR term NOT term
A single term can be combined by Boolean operators: 'AND', 'OR' and 'NOT' ('term1 AND term2' means to query the documents including term1 and term2; 'term1 OR term2' means to query the documents including term1 or term2; 'NOT term1' means to query the documents not including term1). Terms are single words as defined above. You are guaranteed that no non-alphabetic characters appear in a term, and all the terms are in lowercase. Furthermore, some meaningless stop words (common words such as articles, prepositions, and adverbs, specified to be "the, a, to, and, or, not" in our problem) will not appear in the query, either.
For each query, the engine based on the constructed inverted index searches the term in the vocabulary, compares the terms' bucket information, and then gives the result to user. Now can you construct the engine?
Input
The input starts with integer N (0 < N < 100) representing N documents provided. Then the next N sections are N documents. Each section contains the document content and ends with a single line of ten asterisks.
**********
You may assume that each line contains no more than 80 characters and the total number of lines in the N documents will not exceed 1500.
Next, integer M (0 < M ≤ 50000) is given representing the number of queries, followed by M lines, each query in one line. All the queries correspond to the format described above.
Output
For each query, you need to find the document satisfying the query, and output just the lines within the documents that include the search term (For a 'NOT' query, you need to output the whole document). You should print the lines in the same order as they appear in the input. Separate different documents with a single line of 10 dashes.
----------
If no documents matching the query are found, just output a single line: 'Sorry, I found nothing.'. The output of each query ends with a single line of 10 equal signs.
==========
Sample Input
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
Sample Output
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. ==========
HINT
Main idea of the title (from Purple Book):
Enter n articles and M requests (n < 100, m ≤ 50000), and each request is in one of the following four formats.
-
A: Find articles containing keyword a.
-
A AND B: find articles containing both keywords A AND B.
-
A OR B: find articles containing the keyword A OR B.
-
NOT A: find articles that do not contain keyword A.
When handling queries, you need to output evidence for each article. The first three queries output all lines containing at least one keyword, and the fourth query outputs the whole article. Keywords are only composed of lowercase letters. Case is ignored when searching. No more than 80 characters per line, no more than 1500 lines in total.
Because the purple book is very concise, it is directly picked and used.
be careful:
- The search is not case sensitive
- Keywords do not contain non alphabetic characters
- When outputting each instruction, after outputting all the results in an article, output a line of "----------" a total of 10, and 9 on pdf! For each instruction, replace the minus sign with 10 equal signs on the last line of the output result.
Problem solving ideas:
Use map to map the coordinates of each keyword. Use set to store the address coordinate set corresponding to each keyword.
Part of the contents of the instruction can be realized by using the functions of the set set itself: set_union(),set_intersection().
vector<vector>text Store Article content
map<string, set<vector>>point The key is the keyword, and the key value is the address set that appears. Each element of the set is a coordinate array composed of consecutive elements
map<string, set>textid Used to map the article number of each keyword
The first three instructions are output by line and judged by article. Therefore, find the line number of the keyword in the article from each article corresponding to the article number set of the keyword and output it. The output according to the whole article is simple and does not explain.
I thought it would be simpler to use the functions of union set and collection brought by set. I didn't expect to write a lot of code and deal with a lot of details 😂
Accepted
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
vector<vector<string>>text; //Store articles
map<string, set<vector<int>>>point; //Store the coordinates of each keyword
map<string, set<int>>textid; //Store the article number of each keyword
void print(set<int>p,string s1,string s2="") {
if (p.empty())cout << "Sorry, I found nothing." << endl<<"=========="<<endl;//If the collection storing article numbers is empty
else {
for (auto i = p.begin();i != p.end();) {
int flag = 0;
set<vector<int>>p1, p2, p3;
if (point.count(s1))p1 = point[s1]; //The purpose of merging the two key sets into one is to eliminate consecutive keywords in a row
if (point.count(s2))p2 = point[s2]; //And you can also sort the true sum of two sets into one set
set_union(ALL(p1), ALL(p2), INS(p3));
for (auto j = p3.begin();j != p3.end();j++) //The output is one article to another, but there may be other articles in the set corresponding to keywords
if ((*j).front() == (*i)){ //Therefore, judgment is needed
cout << text[(*i)][(*j).back()] << endl;
flag++; //If there is no output, output Sorry
}
if (!flag)cout << "Sorry, I found nothing." << endl;
cout << ((++i) == p.end() ? "==========" : "----------") << endl;
}
}
}
int main() {
int sum,num, c = 0; //Total number of articles and line number of keywords in Articles
string s,s1,s2;
cin >> sum;getchar(); //Eat and enter
for (int i = 0;i < sum;i++) {//Circular entry
vector<string> temp;c = 0;//Initialization, temp is used to store articles
while (getline(cin, s) && s != "**********") {
temp.push_back(s); //Enter each line of the article
for (int j = 0;j < s.size();j++)
if (!isalpha(s[j]))s[j] = ' ';//Convert each line, eat non letters, and convert uppercase letters to lowercase letters
else if(isupper(s[j]))s[j] = s[j] - 'A' + 'a';
stringstream ss(s);
vector<int>id;
id.push_back(i);id.push_back(c); //Record coordinates
while (ss >> s) {
textid[s].insert(i);//Record the article number of each keyword
point[s].insert(id); //Enter coordinates into map
}
c++; //Line number++
}
text.push_back(temp); //Stack articles
}
cin >> num;getchar(); //number of instruction
set<int>p1, p2, p;
for (int i = 0;i < num;i++) {
getline(cin, s);
p1.clear();p2.clear();p.clear();s1.clear();s2.clear();
if (s.find("AND") ==-1&& s.find("OR") ==-1&& s.find("NOT") ==-1) { //If only keywords are included
for (int i = 0;i < s.size();i++) if (isupper(s[i]))s[i] = s[i] - 'A' + 'a';//Convert not lowercase
if (textid.count(s))p = textid[s]; //Take out the article number of the keyword
s1 = s;
}
else{ //If instructions are included
stringstream ss(s);
if (s.find("NOT") != -1) { //If NOT
ss >> s >> s1;
for (int j = 0;j < s1.size();j++)if (isupper(s1[j]))s1[j] = s1[j] - 'A' + 'a';
if (textid.count(s1))p = textid[s1]; //Get article number
if (p.size() == sum) { cout << "Sorry, I found nothing." << endl << "==========" << endl;continue; }
int flag = 0;
for (int j = 0;j < text.size();j++) {
if (!p.count(j)) { //If there is no subscript number of this article in the collection, it will be output
cout << (0 != flag ? "----------\n" : "");
for (int h = 0;h < text[j].size();h++)
cout << text[j][h] << endl;
flag++;
}
}
cout << "==========" << endl;
continue;
}
else {
ss >> s1 >> s >> s2;
for (int j = 0;j < s1.size();j++)if (isupper(s1[j]))s1[j] = s1[j] - 'A' + 'a';//Convert to uppercase
for (int j = 0;j < s2.size();j++)if (isupper(s2[j]))s2[j] = s2[j] - 'A' + 'a';
if (textid.count(s1))p1 = textid[s1]; //Get collection
if (textid.count(s2))p2 = textid[s2];
if(s=="AND")set_intersection(ALL(p1), ALL(p2), INS(p)); //Union set
if(s=="OR") set_union(ALL(p1), ALL(p2), INS(p)); //Sum
}
}
print(p,s1,s2); //Print results
}
}