#include #include #include #include #include #include using namespace std; struct compareWords { bool operator() (const string& left, const string& right) const; }; string lc (string s) { for (int i = 0; i < s.size(); ++i) if (s[i] >= 'A' && s[i] <= 'Z') s[i] += 'a' - 'A'; return s; } bool compareWords::operator() (const string& left, const string& right) const { return lc(left) < lc(right); } struct Sentence { string text; set words; Sentence (const string& sentenceText); private: size_t scanForAlpha (size_t start) const; size_t scanForNonAlpha (size_t start) const; bool isAlpha (char c) const; }; Sentence::Sentence (const string& sentenceText) : text(sentenceText) { size_t start = scanForAlpha(0); while (start < text.size()) { size_t end = scanForNonAlpha(start); string word = text.substr(start, end-start); words.insert (word); start = scanForAlpha(end); } } size_t Sentence::scanForAlpha (size_t start) const { size_t k = start; while (k < text.size() && !isAlpha(text[k])) ++k; return k; } size_t Sentence::scanForNonAlpha (size_t start) const { size_t k = start; while (k < text.size() && isAlpha(text[k])) ++k; return k; } bool Sentence::isAlpha (char c) const { return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z'); } struct Paragraph { vector sentences; Paragraph (const vector& lines); }; Paragraph::Paragraph (const vector& lines) { //cerr << "Building a paragraph from " << lines.size() << " lines" << endl; string sentence; for (int i = 0; i < lines.size(); ++i) { string line = lines[i]; while (true) { while (line[0] == ' ') line = line.substr(1); size_t sentenceEnd = line.find_first_of(".!?"); if (sentenceEnd != string::npos) { sentence = sentence + line.substr(0, sentenceEnd+1); sentences.push_back (Sentence(sentence)); sentence.clear(); line = line.substr(sentenceEnd+1); } else { if (line.size() > 0) sentence = sentence + line + '\n'; break; } } } //cerr << "Paragraph has " << sentences.size() << " sentences" << endl; } typedef vector Document; void readDocument (istream& in, vector& doc, bool& end) { doc.clear(); string line = ""; getline (in, line); while (line != "***" && line != "******") { doc.push_back (line); getline (in, line); } end = (line == "******"); //cerr << "Read document with " << doc.size() << " lines" << endl; } void splitIntoParagraphs (const vector& lines, Document& doc) { vector par; for (int i = 0; i < lines.size(); ++i) { if (lines[i].size() == 0 && par.size() > 0) { doc.push_back (Paragraph(par)); par.clear(); } else { par.push_back (lines[i]); } } if (par.size() > 0) doc.push_back (Paragraph(par)); } string selectTopicSentence (const Paragraph& par) { int bestSoFar = -1; int highestCountSoFar = -1; for (int i = 0; i < par.sentences.size()-1; ++i) { const set& discreteWords = par.sentences[i].words; /* cerr << "evaluating " << i << " "; copy (discreteWords.begin(), discreteWords.end(), ostream_iterator(cerr, " ")); cerr << endl; */ set followingWords; for (int j = i+1; j < par.sentences.size(); ++j) { set theUnion; set_union (followingWords.begin(), followingWords.end(), par.sentences[j].words.begin(), par.sentences[j].words.end(), inserter(theUnion, theUnion.end()), compareWords()); theUnion.swap (followingWords); } /* cerr << "against: "; copy (followingWords.begin(), followingWords.end(), ostream_iterator(cerr, " ")); cerr << endl; */ set intersection; set_intersection (followingWords.begin(), followingWords.end(), discreteWords.begin(), discreteWords.end(), inserter(intersection, intersection.end()), compareWords()); int k = intersection.size(); //cerr << "Score is " << k << endl; if (k > highestCountSoFar) { bestSoFar = i; highestCountSoFar = k; } } return par.sentences[bestSoFar].text; } void printAbstract (const string& text) { cout << text << endl; cout << "======" << endl; } void processDocument (vector& lines) { Document doc; splitIntoParagraphs (lines, doc); string abstract; for (int i = 0; i < doc.size(); ++i) { Paragraph& par = doc[i]; if (par.sentences.size() > 2) { string topic = selectTopicSentence (par); if (abstract.size() > 0) abstract += '\n'; abstract += topic; } } printAbstract (abstract); } void abstract (istream& in) { bool endOfInput = false; while (!endOfInput) { vector rawDocument; readDocument(in, rawDocument, endOfInput); processDocument (rawDocument); } } int main (int argv, char**argc) { abstract (cin); return 0; }