问题描述
p1597原题链接：UVaOJ 1597 - Searching the Web
相关说明：本题为《算法竞赛入门经典（第2版）》习题 5-10
解法一：模拟 + 集合运算
比较繁琐的一题，尤其需要注意：
- 对于每一行最好做些预处理：全部转小写，非字母字符转空格；
- 对于不同类型的 query 分别实现，然后再去重构代码（尽管我懒得去重构了 = =）；
- “交集”表示文章中同时出现了两个关键字，但不要求在同一行；
- “并集”表示文章中出现过两个关键字之一；
- 使用 ---------- 划分 query 结果中不同的文档；
- 使用 ========== 划分不同的 query case.
下面的参考题解写得比较啰嗦，但是所用的数据结构理解性和可读性会好一些，只需要理解 word_pos[word][document_id] 是用来存储和判断对于第 document_id 份文件中存在 word 的行号的集合（可能为空）就行。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; getchar(); // N documents provided. vector<vector<string>> documents(n); // documents -> document -> line map<string, map<int, set<int>>> word_pos; // pos[word][document_id] -> line_id set string line, converted_line, word; for (int i = 0; i < n; i++) { int line_num = 0; while (getline(cin, line) && line != "**********") { documents[i].push_back(line); converted_line = line; for_each(converted_line.begin(), converted_line.end(), [](char &ch) { ch = isalpha(ch) ? tolower(ch) : ' '; }); stringstream words(converted_line); while (words >> word) word_pos[word][i].insert(line_num); line_num++; } } int m; cin >> m; getchar(); // M queries provided. string querry, keyword_a, keyword_b; while (m--) { bool find_something = false; getline(cin, querry); if (querry.find("NOT") != string::npos) { querry = querry.substr(4); for (int i = 0; i < documents.size(); i++) { if (word_pos[querry][i].size() == 0) { cout << (find_something ? "----------\n" : ""); for (auto line : documents[i]) cout << line << endl; find_something = true; } } } else { // AND, OR and just one keyword if (querry.find("AND") != string::npos) { keyword_a = querry.substr(0, querry.find("AND") - 1); keyword_b = querry.substr(querry.find("AND") + 4); for (int i = 0; i < documents.size(); i++) { if (word_pos[keyword_a][i].size() > 0 && word_pos[keyword_b][i].size() > 0) { cout << (find_something ? "----------\n" : ""); set<int> lines; set_union( word_pos[keyword_a][i].begin(), word_pos[keyword_a][i].end(), word_pos[keyword_b][i].begin(), word_pos[keyword_b][i].end(), inserter(lines, lines.begin())); for (auto line : lines) cout << documents[i][line] << endl; find_something = true; } } } else if (querry.find("OR") != string::npos) { keyword_a = querry.substr(0, querry.find("OR") - 1); keyword_b = querry.substr(querry.find("OR") + 3); for (int i = 0; i < documents.size(); i++) { if (word_pos[keyword_a][i].size() > 0 || word_pos[keyword_b][i].size() > 0) { cout << (find_something ? "----------\n" : ""); set<int> lines; set_union( word_pos[keyword_a][i].begin(), word_pos[keyword_a][i].end(), word_pos[keyword_b][i].begin(), word_pos[keyword_b][i].end(), inserter(lines, lines.begin())); for (auto line : lines) cout << documents[i][line] << endl; find_something = true; } } } else { // querry is only one keyword for (int i = 0; i < documents.size(); i++) if (word_pos[querry][i].size() > 0) { cout << (find_something ? "----------\n" : ""); for (auto line : word_pos[querry][i]) cout << documents[i][line] << endl; find_something = true; } } } if (!find_something) cout << "Sorry, I found nothing." << endl; cout << "==========" << endl; } return 0; } |
|
1 |
#TODO |
