UVa 368 Indexing Web Pages

题目描述编写一个程序为小型万维网页集合创建索引。每个“页面”是一种称为HTML \texttt{HTML}HTML超文本标记语言的特殊格式的文本文件。HTML \texttt{HTML}HTML格式包括普通文本和特殊的HTML \texttt{HTML}HTML命令这些命令总是用尖括号括起来。你的程序需要读取名为index.htm的HTML \texttt{HTML}HTML文件读取该文件中所有被HREF命令引用的文件递归地读取这些文件引用的所有文件直到没有新文件可读读取文件webpage.in中的单词列表对于每个单词列出所有包含该单词的文件的文件名假设条件任何左尖括号后面最终都会有一个匹配的右尖括号单词的定义不在尖括号对之间只包含字母无空格、连字符、撇号等不是更长单词的一部分例如balloon中不考虑loon单词最多25 2525个字符大小写不敏感Word、word、WORD视为相同唯一需要关注的HTML \texttt{HTML}HTML命令是HREF格式固定为A HREFfilename文件名不超过12 1212个字符以.htm结尾HTML \texttt{HTML}HTML文件可能相互引用或自引用但最多100 100100个不同文件输入格式初始HTML \texttt{HTML}HTML文件名为index.htm。随后是其他文件包括webpage.in每个文件后跟一个空行。webpage.in中的单词每行一个。输出格式对于每个单词输出如果找到word can be found in the following pages:后跟文件名列表每行一个缩进5 55个空格如果未找到word can not be found in any page.每个单词输出后跟一个空行。样例输入简化HTML ... A HREFlayout.htm ... /HTML A bunch of gibberish and a word ... A HREFindex.htm ...样例输出file can be found in the following pages: index.htm layout.htm index can be found in the following pages: index.htm html can be found in the following pages: index.htm layout.htm recursion can not be found in any page. word can not be found in any page. is can be found in the following pages: index.htm layout.htm题目分析问题的本质这是一个网络爬虫web crawler \texttt{web crawler}web crawler的简化实现。需要递归解析HTML \texttt{HTML}HTML文件提取所有href链接下载读取这些链接指向的文件对每个文件提取其中的单词排除 HTML 标签内容为单词查询建立索引处理流程使用队列BFS \texttt{BFS}BFS处理文件引用对每个文件解析HTML \texttt{HTML}HTML提取单词提取href链接将新文件加入队列读取webpage.in中的查询单词对于每个单词查找包含该单词的文件列表单词提取规则忽略尖括号内的内容HTML \texttt{HTML}HTML标签和注释只考虑连续的字母序列作为单词单词边界由非字母字符分隔大小写处理所有单词转换为小写后再处理。参考代码// Indexing Web Pages// UVa ID: 368// Verdict: Accepted// Submission Date: 2019-01-31// UVa Run Time: 0.000s//// 版权所有C2019邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;setstringvisited;// 已访问的文件vectorstringpages;// 所有访问过的文件列表mapstring,setstringwords;// 文件 - 该文件中的单词集合queuestringq;// BFS 队列string filename,line,content;// 当前文件名、输入行、文件内容// 将字符串转换为小写voidtolower(strings){for(inti0;is.length();i)s[i]std::tolower(s[i]);}// 解析文件内容提取单词和 href 链接voidprocess(){inti0;while(icontent.length()){if(content[i]){// 处理 HTML 标签i;string block;while(icontent.length()content[i]!){blockcontent[i];i;}// 检查是否是 href 链接if(block.length()13){if(block.substr(0,8)A HREF\block.back()){string pageblock.substr(8,block.length()-9);// 如果未访问过加入队列if(visited.find(page)visited.end()){visited.insert(page);pages.push_back(page);q.push(page);}}}}elseif(isalpha(content[i])){// 提取单词连续字母string w;while(icontent.length()isalpha(content[i])){wcontent[i];i;}tolower(w);// 转换为小写words[filename].insert(w);}else{i;}}}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);// BFS 遍历所有文件从 index.htm 开始visited.insert(index.htm);pages.push_back(index.htm);q.push(index.htm);while(!q.empty()){filenameq.front();q.pop();content.clear();// 读取文件内容直到空行while(getline(cin,line),line.length()0){contentline;content\n;}// 解析文件内容process();}// 处理查询单词string w;intcases0;while(cinw){if(cases)cout\n;coutw;string lower_ww;tolower(lower_w);// 查找包含该单词的文件vectorstringlists;for(autofs:pages){if(words[fs].find(lower_w)!words[fs].end())lists.push_back(fs);}if(lists.size()0)cout can not be found in any page.\n;else{cout can be found in the following pages:\n;for(autols:lists)cout ls\n;}}return0;}