Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #if defined __GNUC__ || defined __APPLE__
- #include <ext/hash_map>
- #else
- #include <hash_map>
- #endif
- #include <vector>
- #include <string>
- #include <math.h>
- #include <cstdlib>
- #include <algorithm>
- #include <string.h>
- #define MAX_BUF 100000
- using namespace std;
- using namespace __gnu_cxx; // hash_map
- typedef unsigned int uint;
- struct stringHash {
- size_t operator()(const string& p) const {
- size_t h = 0;
- for(int i = 0 ; i < p.length(); i++)
- {
- h = (h<<1)^p[i];
- }
- return h;
- }
- };
- struct stringEqual {
- bool operator()(const string& c1, const string& c2) const {
- return c1.compare(c2) == 0;
- }
- };
- class Word
- {
- private:
- string word;
- string number;
- public:
- uint rating;
- Word(string w, string num, uint r): word(w), number(num), rating(r) {}
- string get_word() { return word; }
- };
- // Comparing function for sorting
- bool compare(Word a, Word b)
- {
- if (a.rating > b.rating) return true;
- else
- {
- if(a.rating == b.rating && (a.get_word().compare(b.get_word()) < 0)) return true;
- }
- return false;
- }
- class Dictionary
- {
- private:
- hash_map<string, vector<Word>, stringHash, stringEqual > dict; // there are also implementations with list<Word> and list<Word*>
- string specials;
- vector<Word>::iterator get_from_position(string, uint);
- vector<Word>::iterator find_position_to_insert(vector<Word>::iterator, string);
- public:
- string number_from_word(string);
- Dictionary() : dict(), specials(".,?") { };
- void add_word(string, uint);
- string get_word(string, uint);
- void sort();
- } dict;
- void Dictionary::sort()
- {
- for(hash_map<string, vector<Word>, stringHash, stringEqual>::iterator it = dict.begin(); it != dict.end(); ++it)
- {
- std::sort(it->second.begin(), it->second.end(), compare);
- }
- }
- string Dictionary::number_from_word(string word)
- {
- string number = "";
- for(uint i = 0; i < word.length(); i++)
- {
- switch(word[i])
- {
- case 'a': case 'b': case 'c':
- number += "2"; break;
- case 'd': case 'e': case 'f':
- number += "3"; break;
- case 'g': case 'h': case 'i':
- number += "4"; break;
- case 'j': case 'k': case 'l':
- number += "5"; break;
- case 'm': case 'n': case 'o':
- number += "6"; break;
- case 'p': case 'q': case 'r': case 's':
- number += "7"; break;
- case 't': case 'u': case 'v':
- number += "8"; break;
- case 'w': case 'x': case 'y': case 'z':
- number += "9"; break;
- }
- }
- return number;
- }
- void Dictionary::add_word(string word, uint rating)
- {
- string num = number_from_word(word);
- Word w = Word(word, num, rating);
- if (dict.count(num) > 0)
- {
- dict[num].push_back(w);
- }
- else dict[num].push_back(w);
- }
- vector<Word>::iterator Dictionary::get_from_position(string num, uint pos)
- {
- return dict[num].begin() + pos;
- }
- vector<Word>::iterator Dictionary::find_position_to_insert(vector<Word>::iterator it, string num)
- {
- vector<Word>::iterator pos = it;
- if(dict[num].size() == 2)
- {
- if(pos != dict[num].begin() && (--pos)->rating > it->rating) return ++pos;
- }
- while ( pos->rating <= it->rating )
- {
- if (pos == dict[num].begin()) return dict[num].begin();
- -- pos;
- if( pos -> rating > it -> rating) return ++pos;
- }
- return pos;
- }
- string Dictionary::get_word(string num, uint pos)
- {
- if(num == "1")
- {
- cout<< specials[pos];
- return "";
- }
- else
- {
- vector<Word>::iterator it = get_from_position(num, pos);
- string word = it->get_word();
- uint r = ++ it->rating;
- if(dict[num].size() > 1)
- {
- vector<Word>::iterator i_pos = find_position_to_insert(it, num);
- if(it != i_pos)
- {
- dict[num].erase(it);
- dict[num].insert(i_pos, Word(word, num, r));
- }
- }
- return word;
- }
- }
- int main (int argc, const char * argv[])
- {
- uint N;
- cin >> N;
- string word;
- uint rating;
- for(uint i = 0; i < N; i++)
- {
- cin >> word >> rating;
- dict.add_word(word, rating);
- }
- dict.sort();
- char str[MAX_BUF];
- cin.get(); // last \n in from last word
- cin.getline(str, MAX_BUF);
- string stack("");
- stack.reserve(20);
- uint pos = 0;
- for (size_t i = 0; i < strlen(str); ++i)
- {
- if (isdigit(str[i]))
- {
- if(str[i] != '1')
- {
- if (stack != "1") stack += str[i];
- else
- {
- cout << dict.get_word(stack, pos);
- stack = "";
- stack += str[i];
- pos = 0;
- }
- }
- else
- {
- if(!stack.empty()) cout << dict.get_word(stack, pos);
- stack = "1";
- pos = 0;
- }
- }
- else if (str[i] == '*') ++pos;
- else if (str[i] == ' ')
- {
- if(!stack.empty()) cout << dict.get_word(stack, pos);
- cout<<" ";
- stack = "";
- pos = 0;
- }
- }
- if(!stack.empty()) cout << dict.get_word(stack, pos) << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement