紫书刷题进行中,题解系列【
GitHub
|
CSDN
】
习题5-10 UVA1597 Searching the Web(65行AC代码)
题目大意
给定若干篇有编号的文章,构造一个搜索引擎,处理查询命令。
搜索引擎构造
原题描述中的
Figure-1
说得很清楚,即对于每个单词,将它出现的地方以**(文章编号,行号)**形式记录。
同时题目对问题做了简化:
-
每个单词仅包含26个字母,其余字符(包括
数字,连字符
)均可看成空格 - 不考虑时态问题,大小不敏感(全转为小写)
命令格式
输出时均按输入文章时的顺序,注意单词所在文章和行的区别
-
term
:直接输出term所在行 -
term1 AND term2
:求两个单词所在
文章交集
,将
交集文章中对应的行全部输出
-
term OR term
:求两个单词所在
行的并集
-
NOT term
:将不包含单词的文章
整篇输出
算法设计
定义如下数据结构分别存储
每个单词对应的文章id和行号
,
每篇文章的每一行
map<string, vector<pair<int,int> > > mp; // 单词->(文章id,行号)
vector<string> doc[110]; // 文本
在读入每行字符串时,将非26字母表中的字符全部转为空格,然后用
stringstream
分割得到每个单词对应位置,较容易完成搜索引擎构造。
对于
与或非
命令可用
集合交并补
方式处理,比较简单
注意点
- 按文章输入顺序输出相应行/文章
-
不同文章的句子需10个
-
分隔 -
在遍历
set/map
过程中,不要进行删除操作,否则会
RE
- 提取不同命令的共性,简化代码
- 先写结构,再逐步细化,瀑布式开发,写一点测试一点
AC代码(C++11,字符串处理,map)
#include<bits/stdc++.h>
using namespace std;
int N, M;
string s, st, t1, t2;
map<string, vector<pair<int,int> > > mp; // 单词->(文章id,行号)
vector<string> doc[110]; // 文本
int main() {
cin >>N; getchar(); // 吸收换行
for (int i = 0; i < N; i ++) { // 所有文本
int line=0; // 行号
while (getline(cin ,s) && s[0] != '*') {
doc[i].push_back(s); // 文本i的第line行
for (auto& ch : s)
if (!isalpha(ch)) ch = ' '; // 非字母全换为空格
else ch = tolower(ch); // 字母均转为小写
stringstream input(s); // 空格分割
while (input >>s) mp[s].push_back({i, line}); // word所在文本编号和行号
line ++; // 行号增加
}
}
cin >>M; getchar();
while (M --) { // 查询处理
getline(cin, s); // 查询
int i = s.find(' '), j = s.rfind(' '); // 从首,尾开始遇见的第一个空格位置
set<pair<int,int> > out; // 输出集合
if (i == string::npos) out.insert(mp[s].begin(), mp[s].end()); // term
else { // 与或非
if (s[0] == 'N') { // NOT
t1 = s.substr(i+1);
set<int> _set;
for (int i = 0; i < N; i ++) _set.insert(i); // 所有文章id
for (auto p : mp[t1]) _set.erase(p.first); // 删除包含t1的文章id
for (auto p : _set) { // 输出整篇文章
for (auto line : doc[p]) cout <<line <<endl; // 打印不包含t1的所有整篇文章
if (p != *_set.rbegin()) cout <<"----------"<<endl; // 不同文章需间隔
}
if (_set.empty()) cout <<"Sorry, I found nothing.\n"; // 空处理
}
else { // AND,OR
t1 = s.substr(0, i); // term1
t2 = s.substr(j+1); // term2
out.insert(mp[t1].begin(), mp[t1].end()); // 求并集
out.insert(mp[t2].begin(), mp[t2].end());
if (j - i - 1 == 3) { // AND,求交集
set<int> set1, set2;
for (auto p : mp[t1]) set1.insert(p.first); // t1所在文本
for (auto p : mp[t2]) if (set1.find(p.first) != set1.end()) set2.insert(p.first); // 求交集文本
auto tmp = out; // 先备份,再删除;若边删边遍历会RE
for (auto p : tmp) if (set2.find(p.first) == set2.end()) out.erase(p); // 删除不相交的
}
}
}
int pre=-1; // 控制间隔输出
if (s[0] != 'N') { // 非NOT语句统一输出
for (auto p : out) {
if (pre != -1 && pre != p.first) cout <<"----------"<<endl; // 两个不同文章之间
pre = p.first;
cout <<doc[p.first][p.second] <<endl;
}
if (out.empty()) cout <<"Sorry, I found nothing.\n";
}
cout <<"==========" <<endl;
}
return 0;
}
版权声明:本文为qq_40738840原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。