POJ 1598 - Excuses, Excuses!

http://poj.org/problem?id=1598

概要

\(k\) 個のキーワードと \(E\) 個の文が与えられる。 与えられた文のうち、最も多くキーワードを含む文をすべて答える。 同じキーワードが複数回出現したときは重複して数える。 また、キーワードは大文字と小文字の区別はしないこととする。

制約

解法

やるだけ。

 1 #include <iostream>
 2 #include <sstream>
 3 #include <vector>
 4 #include <set>
 5 #include <cctype>
 6 #include <iterator>
 7 #include <algorithm>
 8 using namespace std;
 9 
10 char downcase(char c) { return tolower(c); }
11 char cleanup(char c) { return isalpha(c) ? tolower(c) : ' '; }
12 
13 int main()
14 {
15   ios::sync_with_stdio(false);
16   for (int K, E, Ti = 1; cin >> K >> E; Ti++) {
17     set<string> keywords;
18     for (int i = 0; i < K; i++) {
19       string s;
20       cin >> s;
21       transform(s.begin(), s.end(), s.begin(), downcase);
22       keywords.insert(s);
23     }
24 
25     cin.ignore();
26     vector<string> ans;
27     int m = 0;
28     for (int i = 0; i < E; i++) {
29       string line;
30       getline(cin, line);
31       const string orig_line = line;
32       transform(line.begin(), line.end(), line.begin(), cleanup);
33       istringstream iss(line);
34       int c = 0;
35       for (string s; iss >> s;) {
36         if (keywords.count(s)) {
37           ++c;
38         }
39       }
40       if (c > m) {
41         m = c;
42         ans.clear();
43         ans.push_back(orig_line);
44       } else if (c == m) {
45         ans.push_back(orig_line);
46       }
47     }
48     cout << "Excuse Set #" << Ti << endl;
49     copy(ans.begin(), ans.end(), ostream_iterator<string>(cout, "\n"));
50     cout << endl;
51   }
52   return 0;
53 }
poj/1598.cc