Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Aug 28th, 2011  |  syntax: C++  |  size: 6.05 KB  |  views: 645  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <iostream>
  2.  
  3. #if defined __GNUC__ || defined __APPLE__
  4.     #include <ext/hash_map>
  5. #else
  6.     #include <hash_map>
  7. #endif
  8.  
  9. #include <vector>
  10. #include <string>
  11. #include <math.h>
  12. #include <cstdlib>
  13. #include <algorithm>
  14. #include <string.h>
  15.  
  16. #define MAX_BUF 100000
  17.  
  18. using namespace std;
  19. using namespace __gnu_cxx; // hash_map
  20. typedef unsigned int uint;
  21.  
  22.  
  23. struct stringHash {
  24.     size_t operator()(const string& p) const {
  25.         size_t h = 0;
  26.        
  27.         for(int i = 0 ; i < p.length(); i++)
  28.         {
  29.             h = (h<<1)^p[i];
  30.         }
  31.         return h;
  32.     }
  33. };
  34.  
  35. struct stringEqual {
  36.     bool operator()(const string& c1, const string& c2) const {
  37.         return c1.compare(c2) == 0;
  38.     }
  39. };
  40.  
  41.  
  42. class Word
  43. {
  44. private:
  45.     string word;
  46.     string number;
  47.    
  48.    
  49. public:
  50.     uint rating;
  51.    
  52.     Word(string w, string num, uint r): word(w), number(num), rating(r) {}    
  53.    
  54.     string get_word() { return word;   }
  55.    
  56. };
  57.  
  58. // Comparing function for sorting
  59. bool compare(Word a, Word b)
  60. {
  61.     if (a.rating > b.rating) return true;
  62.     else
  63.     {
  64.         if(a.rating == b.rating && (a.get_word().compare(b.get_word()) < 0)) return true;
  65.     }
  66.     return false;
  67. }
  68.  
  69.  
  70.  
  71. class Dictionary
  72. {
  73. private:
  74.     hash_map<string, vector<Word>, stringHash, stringEqual > dict; // there are also implementations with list<Word> and list<Word*>
  75.     string specials;
  76.    
  77.    
  78.     vector<Word>::iterator get_from_position(string, uint);
  79.    
  80.     vector<Word>::iterator find_position_to_insert(vector<Word>::iterator, string);
  81.    
  82. public:
  83.     string number_from_word(string);
  84.    
  85.     Dictionary() : dict(), specials(".,?") { };
  86.    
  87.     void add_word(string, uint);
  88.     string get_word(string, uint);    
  89.    
  90.     void sort();
  91.        
  92. } dict;
  93.  
  94.  
  95. void Dictionary::sort()
  96. {
  97.     for(hash_map<string, vector<Word>, stringHash, stringEqual>::iterator it = dict.begin(); it != dict.end(); ++it)
  98.     {
  99.         std::sort(it->second.begin(), it->second.end(), compare);
  100.     }
  101. }
  102.  
  103. string Dictionary::number_from_word(string word)
  104. {
  105.     string number = "";
  106.    
  107.     for(uint i = 0; i < word.length(); i++)
  108.     {
  109.         switch(word[i])
  110.         {
  111.             case 'a': case 'b': case 'c':
  112.                 number += "2"; break;
  113.                
  114.             case 'd': case 'e': case 'f':
  115.                 number += "3"; break;
  116.                
  117.             case 'g': case 'h': case 'i':
  118.                 number += "4"; break;
  119.                
  120.             case 'j': case 'k': case 'l':
  121.                 number += "5"; break;
  122.                
  123.             case 'm': case 'n': case 'o':
  124.                 number += "6"; break;
  125.                
  126.             case 'p': case 'q': case 'r': case 's':
  127.                 number += "7"; break;
  128.                
  129.             case 't': case 'u': case 'v':
  130.                 number += "8"; break;
  131.                
  132.             case 'w': case 'x': case 'y': case 'z':
  133.                 number += "9"; break;
  134.         }
  135.     }
  136.    
  137.     return number;
  138. }
  139.  
  140. void Dictionary::add_word(string word, uint rating)
  141. {
  142.     string num = number_from_word(word);
  143.    
  144.     Word w = Word(word, num, rating);
  145.     if (dict.count(num) > 0)
  146.     {
  147.         dict[num].push_back(w);
  148.     }
  149.     else dict[num].push_back(w);
  150. }
  151.  
  152. vector<Word>::iterator Dictionary::get_from_position(string num, uint pos)
  153. {
  154.     return dict[num].begin() + pos;
  155. }
  156.  
  157. vector<Word>::iterator Dictionary::find_position_to_insert(vector<Word>::iterator it, string num)
  158. {
  159.     vector<Word>::iterator pos = it;
  160.    
  161.     if(dict[num].size() == 2)
  162.     {
  163.         if(pos != dict[num].begin() && (--pos)->rating > it->rating) return ++pos;
  164.     }
  165.    
  166.    
  167.     while ( pos->rating <= it->rating )
  168.     {
  169.         if (pos == dict[num].begin()) return dict[num].begin();
  170.        
  171.         -- pos;
  172.         if( pos -> rating > it -> rating) return ++pos;
  173.     }
  174.    
  175.    
  176.     return pos;
  177. }
  178.  
  179. string Dictionary::get_word(string num, uint pos)
  180. {
  181.     if(num == "1")
  182.     {
  183.         cout<< specials[pos];
  184.         return "";
  185.     }
  186.     else
  187.     {
  188.         vector<Word>::iterator it = get_from_position(num, pos);
  189.        
  190.         string word = it->get_word();
  191.        
  192.         uint r = ++ it->rating;
  193.        
  194.         if(dict[num].size() > 1)
  195.         {
  196.            
  197.             vector<Word>::iterator i_pos = find_position_to_insert(it, num);
  198.            
  199.             if(it != i_pos)
  200.             {
  201.                 dict[num].erase(it);
  202.                 dict[num].insert(i_pos, Word(word, num, r));
  203.             }
  204.         }
  205.        
  206.         return word;
  207.     }
  208. }
  209.  
  210.  
  211.  
  212.  
  213. int main (int argc, const char * argv[])
  214. {
  215.     uint N;
  216.     cin >> N;
  217.    
  218.    
  219.     string word;
  220.     uint rating;
  221.     for(uint i = 0; i < N; i++)
  222.     {
  223.         cin >> word >> rating;
  224.        
  225.         dict.add_word(word, rating);
  226.     }
  227.    
  228.     dict.sort();
  229.    
  230.     char str[MAX_BUF];
  231.     cin.get(); // last \n in from last word
  232.     cin.getline(str, MAX_BUF);
  233.        
  234.    
  235.     string stack("");
  236.     stack.reserve(20);
  237.    
  238.     uint pos = 0;
  239.    
  240.     for (size_t i = 0; i < strlen(str); ++i)
  241.     {
  242.         if (isdigit(str[i]))
  243.         {
  244.            
  245.             if(str[i] != '1')
  246.             {
  247.                 if (stack != "1") stack += str[i];
  248.                 else
  249.                 {
  250.                     cout << dict.get_word(stack, pos);
  251.                     stack = "";
  252.                     stack += str[i];
  253.                     pos = 0;
  254.                 }
  255.             }
  256.             else
  257.             {
  258.                 if(!stack.empty()) cout << dict.get_word(stack, pos);
  259.                
  260.                 stack = "1";
  261.                 pos = 0;
  262.             }
  263.         }
  264.         else if (str[i] == '*') ++pos;
  265.         else if (str[i] == ' ')
  266.         {
  267.             if(!stack.empty()) cout << dict.get_word(stack, pos);
  268.            
  269.             cout<<" ";
  270.            
  271.             stack = "";
  272.             pos = 0;
  273.         }
  274.     }
  275.    
  276.     if(!stack.empty()) cout << dict.get_word(stack, pos) << endl;
  277.  
  278.    
  279.    
  280.     return 0;
  281. }