题目：https://vjudge.net/problem/UVA-1597
思路：刚开始用string.find()暴力查找，然后果不其然的超时了，之后改用map过了。 用vector< string >的数组data储存原文章，每个数组元素存储一篇文章，又用了一个从单词到单词所在篇目和每个篇目所在行的映射，之后按要求进行查找输出即可。
注：这题细节问题很多 （1）关于输出格式，题目给的PDF的输出样例 “———-”应该是10个“-”结果样例是9个。。。。 还有——的输出时机也要注意。 （2）要查找的单词只有英文，不包括英文字母外的任何符号，我的方法是把每行!isalpha()的字符全换成空格在利用stringstream流式读入。原本用的!isalnum()错了。。。
代码：C++11
#include <iostream> #include <string> #include <cstdio> #include <cctype> #include <iomanip> #include <map> #include <set> #include <vector> #include <deque> #include <cstring> #include <algorithm> #include <sstream> using namespace std; const string END("**********"); vector<string> data[110]; map<string, map<int, set<int> > > database; void str_lower(string &s) { for(auto &t:s) { if(isupper(t)) { t = tolower(t); } } } void get_passage(int n) { for(int i=0; i<n; i++) { for(int j=0; ; j++) { string s; getline(cin, s); if(s==END) { break; } data[i].push_back(s); for(auto &t:s) { if(!isalpha(t)) { t = ' '; } } stringstream ss; ss << s; while(ss >> s) { str_lower(s); database[s][i].insert(j); } } } } void find_A(const string &A, int n) { if(database.count(A)==0) { cout << "Sorry, I found nothing." << endl; } else { bool flag = false; for(auto &t:database[A]) { if(flag) { cout << "----------" << endl; } flag = true; for(int temp:t.second) { cout << data[t.first][temp] << endl; } } } } void A_and_B(const string &A, const string &B, int n) { bool flag = false; bool firstpassage = true; if(database.count(A)!=0) { for(auto &t:database[A]) { if(database.count(B)!=0&&database[B].count(t.first)!=0) { flag = true; if(!firstpassage) { cout << "----------" << endl; } firstpassage = false; set<int> ans; set_union(database[A][t.first].begin(), database[A][t.first].end(), database[B][t.first].begin(), database[B][t.first].end(), inserter(ans, ans.begin())); for(auto temp:ans) { cout << data[t.first][temp] << endl; } } } } if(!flag) { cout << "Sorry, I found nothing." << endl; } } void A_or_B(const string &A, const string &B, int n) { map<int, set<int> > ans; if(database.count(A)!=0) { for(auto &t:database[A]) { for(int temp:t.second) { ans[t.first].insert(temp); } } } if(database.count(B)!=0) { for(auto &t:database[B]) { for(int temp:t.second) { ans[t.first].insert(temp); } } } if(ans.empty()) { cout << "Sorry, I found nothing." << endl; } else { bool firstpassage = true; for(auto &t:ans) { if(!firstpassage) { cout << "----------" << endl; } firstpassage = false; for(auto temp:t.second) { cout << data[t.first][temp] << endl; } } } } void without_A(const string &A, int n) { set<int> all; for(int i=0; i<n; i++) { all.insert(i); } set<int> Apassage; if(database.count(A)!=0) { for(auto &t:database[A]) { Apassage.insert(t.first); } } set<int> ans; set_difference(all.begin(), all.end(), Apassage.begin(), Apassage.end(), inserter(ans, ans.begin())); if(ans.empty()) { cout << "Sorry, I found nothing." << endl; } else { bool firstpassage = true; for(auto &t:ans) { if(!firstpassage) { cout << "----------" << endl; } firstpassage = false; for(auto &temp:data[t]) { cout << temp << endl; } } } } int main() { int n; cin >> n; getchar(); get_passage(n); int m; cin >> m; getchar(); while(m--) { string A, B, s; stringstream ss; getline(cin, s); ss << s; ss >> A; if(A=="NOT") { ss >> A; without_A(A, n); } else if(ss >> s >> B) { if(s=="AND") { A_and_B(A, B, n); } else { A_or_B(A, B, n); } } else { find_A(A, n); } cout << "==========" << endl; } return 0; }