博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
uva 1597 Searching the Web
阅读量:5867 次
发布时间:2019-06-19

本文共 10908 字,大约阅读时间需要 36 分钟。

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

4A 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?**********6computerbooks AND computerbooks OR protectedNOT securityveryslick

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.========== 代码超时,改进后仍然超时,以下是交了两次后的超时代码
#include 
#include
#include
#include
#include
#include
using namespace std;vector
lines[105][1505]; //共不超过100篇文章,每篇文章不超过1500行vector
::iterator t;int line_num[105], N; //line_num每篇文章的行数,Nbool strCmp(const string a , const string b) //将a ,b都转化为大写字母比较,若相同返回true{ int aLen = a.length(); int bLen = b.length(); bool flag = true; int p = 0; if(!isalpha(b[0]))p = 1; //cout << a<<"a b--"<
<
< aLen;i++){ if(tolower(a[i]) != tolower(b[p++])){ flag = false; break; } } if(flag && p < bLen){ if(isalpha(b[p]))flag = false; } return flag;}bool deal_find(string a,int p, int q) //在一行中查找a,若存在返回true{ for(t = lines[p][q].begin();t != lines[p][q].end();t++){ if(strCmp(a,*t))return true; } return false;}void output(int i,int j){ for(t = lines[i][j].begin();t != lines[i][j].end();t++){ if( t == lines[i][j].begin())cout<<*t; else cout<<" "<<*t; } cout<
and_line; for(int j = 0; j < line_num[i]; j++){ if(deal_find(a,i,j)){ a0 = 1; and_line.insert(j); } if(deal_find(b,i,j)){ b0 = 1; and_line.insert(j); } } if(a0 && b0){ re = true; if(flag)cout<<"----------"<
::iterator iter; for(iter=and_line.begin();iter!=and_line.end();iter++)output(i,*iter); } } return re;}bool NOT(string a){ bool flag , re = false, k = false; for(int i = 0; i < N; i++){ flag = false; for(int j = 0; j < line_num[i]; j++){ if(deal_find(a,i,j)){ flag = true; break; } } if(flag)continue; else{ re = true; if(k)cout<<"----------"<
< line_num[i]; j++)output(i,j); } } return re;}int main(){ int num1 = 0, M; cin >> N; int n = N; while(n--){ //n篇文章输入 int num2 = 0; string line; while((getline(cin,line)) != NULL){ bool flag = true; stringstream ss(line); string word; while(ss >> word){ if( word[0] == '*' ){ flag = false; break; } lines[num1][num2].push_back(word); } if(!flag)break; num2++; } line_num[num1] = num2; num1++; } cin >> M; bool re1,re2; string com; getchar(); while(M--){ getline(cin, com); if(com.find("AND") != string::npos){ re1 = AND(com.substr(0,com.find_first_of(' ')), com.substr(com.find_last_of(' ')+1)); if(!re1)cout << "Sorry, I found nothing."<
<< endl; } //system("pause"); return 0;}
最后分别在VS,CB上运行,发现主函数的返回值有问题,程序已经运行结束,然而程序仍没有退出。出现以下情况 需要再点一次回车 然后
程序内部的错误吧........越来越不懂计算机了....T_T 接下来又继续改,已经没有上面的问题了,而且感觉结果正确,但是!!!!!还是超时了!!!!
#include 
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;vector
lines[105][1505]; //共不超过100篇文章,每篇文章不超过1500行vector
::iterator t;int line_num[105], N;#define FILEbool deal_find(string a,int p, int q) //在一行中查找a,若存在返回true{ for(t = lines[p][q].begin();t != lines[p][q].end();t++){ int aLen = a.length(), bLen = (*t).length(); bool flag = true; int p = 0; if(!isalpha((*t)[0]))p = 1; for(int i = 0;i < aLen;i++){ if(tolower(a[i]) != tolower((*t)[p++])){ flag = false; break; } } if(flag && p < bLen){ if(isalpha((*t)[p]))flag = false; } if(flag)return true; } return false;}void output(int i,int j){ for(t = lines[i][j].begin();t != lines[i][j].end();t++){ if( t == lines[i][j].begin())cout<<*t; else cout<<" "<<*t; } cout<
and_line; for(int j = 0; j < line_num[i]; j++){ if(deal_find(a,i,j)){ a0 = 1; and_line.insert(j); } if(deal_find(b,i,j)){ b0 = 1; and_line.insert(j); } } if(a0 && b0){ re = true; if(flag)cout<<"----------"<
::iterator iter; for(iter=and_line.begin();iter!=and_line.end();iter++)output(i,*iter); } } return re;}bool OR(string a, string b){ bool flag = false, re = false; for(int i = 0; i < N; i++){ flag = true; int k = 1; for(int j = 0; j < line_num[i]; j++){ if(deal_find(a,i,j)){ if(flag&&k&&re){ cout<<"----------"<
< line_num[i]; j++){ output(i,j); } } } return re;}int main(int argc, char* argv[]){ int M, num1 = 0,num2 = 0; string line; cin >> N; cin.get(); for(int i = 0; i
> word)lines[num1][num2].push_back(word); num2++; } line_num[num1] = num2; num1++; } cin >> M; bool re1,re2; string com; cin.get(); for(int i=0;i
 

醉了,这下足以说明是思路的问题了,思路不正确导致超时。

 

 
 

 

 

转载于:https://www.cnblogs.com/farewell-farewell/p/5477459.html

你可能感兴趣的文章
获取AFP共享的文件夹及其权限
查看>>
安装Ubuntu虚拟系统
查看>>
访问网站出现图片破裂
查看>>
安装gulp及相关插件
查看>>
如何在Linux用chmod来修改所有子目录中的文件属性?
查看>>
项目: Zabbix监控搭建部署
查看>>
Windows7配置python环境变量
查看>>
学习mysql
查看>>
Applet
查看>>
gNewsense设置自动登录
查看>>
poj1919--Red and Black (DFS)
查看>>
iostream与iostream.h的区别
查看>>
JS实现简易图片轮播效果的方法
查看>>
Java微信公众平台开发(十三)--微信JSSDK中Config配置
查看>>
移动端链接、点击事件、输入框去除背景高亮
查看>>
SQL 优化原则(转)
查看>>
神奇代码
查看>>
android pop3与imap方式接收邮件(javamail)
查看>>
RabbitMQ消息队列(二):"Hello, World"[转]
查看>>
如果不能显示真正的考验个别车型toast问题解决
查看>>