POJ 2162 - Document Indexing

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

概要

与えられた文章を \(n\) 行ずつページに分割し、どの単語が何ページ目に登場しているかを答える。

文章は一行の空行によってパラグラフに分割されており、ページの境界とパラグラフの境界の関係でいくつか特別なルールがあるので、それを守るようにページを分割しなければならない (説明がとてもめんどくさいので問題文を参照)。

制約

解法

注意深くがんばって実装する。

  1 #include <iostream>
  2 #include <sstream>
  3 #include <vector>
  4 #include <map>
  5 #include <cctype>
  6 #include <algorithm>
  7 using namespace std;
  8 
  9 int main()
 10 {
 11   ios::sync_with_stdio(false);
 12   int N;
 13   cin >> N;
 14   cin.ignore();
 15 
 16   vector<string> lines;
 17   for (string line; getline(cin, line);) {
 18     lines.push_back(line);
 19   }
 20   const int M = lines.size();
 21 
 22   vector<string> pages;
 23   int i;
 24   for (i = N; i < M; i += N) {
 25     string page;
 26     if (lines[i].empty()) {
 27       // rule 1
 28       for (int j = i-N; j < i; j++) {
 29         page += " " + lines[j];
 30       }
 31       pages.push_back(page);
 32       ++i;
 33     } else if (!lines[i-1].empty() && (i+1 == M || (i+1 < M && lines[i+1].empty()))) {
 34       if (lines[i-2].empty() || lines[i-3].empty()) {
 35         // rule 4
 36         for (int j = i-N; j < i-2; j++) {
 37           page += " " + lines[j];
 38         }
 39         pages.push_back(page);
 40         if (lines[i-2].empty()) {
 41           i -= 1;
 42         } else {
 43           i -= 2;
 44         }
 45       } else {
 46         // rule 3
 47         for (int j = i-N; j < i-1; j++) {
 48           page += " " + lines[j];
 49         }
 50         pages.push_back(page);
 51         --i;
 52       }
 53     } else if (lines[i-2].empty() && !lines[i-1].empty()
 54         && !lines[i].empty() && i+1 < M && !lines[i+1].empty()) {
 55       // rule 2
 56       for (int j = i-N; j < i-1; j++) {
 57         page += " " + lines[j];
 58       }
 59       pages.push_back(page);
 60       --i;
 61     } else {
 62       for (int j = i-N; j < i; j++) {
 63         page += " " + lines[j];
 64       }
 65       pages.push_back(page);
 66     }
 67   }
 68   string buf;
 69   for (i -= N; i < M; i++) {
 70     buf += " " + lines[i];
 71   }
 72   pages.push_back(buf);
 73 
 74   map<string, vector<int> > dict;
 75   const int P = pages.size();
 76   for (i = 0; i < P; i++) {
 77     vector<string> v;
 78     buf = "";
 79     for (string::const_iterator it = pages[i].begin(); it != pages[i].end(); ++it) {
 80       if (isalpha(*it)) {
 81         buf += toupper(*it);
 82       } else {
 83         if (!buf.empty()) {
 84           v.push_back(buf);
 85         }
 86         buf.clear();
 87       }
 88     }
 89     if (!buf.empty()) {
 90       v.push_back(buf);
 91     }
 92     sort(v.begin(), v.end());
 93     v.erase(unique(v.begin(), v.end()), v.end());
 94     for (vector<string>::const_iterator it = v.begin(); it != v.end(); ++it) {
 95       dict[*it].push_back(i+1);
 96     }
 97   }
 98   for (map<string, vector<int> >::const_iterator it = dict.begin(); it != dict.end(); ++it) {
 99     cout << it->first << " ";
100     const vector<int>& v = it->second;
101     vector<pair<int,int> > ans;
102     ans.push_back(make_pair(v[0], v[0]));
103     for (vector<int>::const_iterator jt = v.begin()+1; jt != v.end(); ++jt) {
104       if (*jt == ans.back().second+1) {
105         ++ans.back().second;
106       } else {
107         ans.push_back(make_pair(*jt, *jt));
108       }
109     }
110     for (vector<pair<int,int> >::const_iterator jt = ans.begin(); jt != ans.end(); ++jt) {
111       if (jt != ans.begin()) {
112         cout << ",";
113       }
114       if (jt->first == jt->second) {
115         cout << jt->first;
116       } else if (jt->first+1 == jt->second) {
117         cout << jt->first << "," << jt->second;
118       } else {
119         cout << jt->first << "-" << jt->second;
120       }
121     }
122     cout << endl;
123   }
124   return 0;
125 }
poj/2162.cc