Talk:UVa 10226

http://acm.uva.es/p/v102/10226.html

Summary

All you have to do is: search a word in a list, if the word is not a member of the list then you have to add that with a counter initialize with 1 otherwise if the word is in the list then you need to increment its counter by one. And finally the output is the percentage of every unique word.

You can increment a counter in a map<string, int> without first checking for its existence, which may make your code faster, as you do fewer map lookups. The following is legitimate, working code.

#include <map>
#include <string>
#include <iostream>

using namespace std;

int main() {
  string tmp;
  map<string, int> hist;
  while (cin >> tmp) {
    hist[tmp]++;
  }
  for (map<string, int>::iterator it = hist.begin(); it != hist.end(); ++it) {
    cout << it->first << " " << it->second << "\n";
  }
}

--Rrenaud 12:19, 10 Apr 2006 (EDT)

Explanation

Many people tried to solve this problem using stl mapping. But got TLE because map is very slow. My suggestion is try to solve this using Trie algorithm where complexity of searching or inserting a word is O(n) [n is the lenth of the word]

--Mahbub 10:10, 9 Apr 2006 (EDT)

Actually, I did it with STL map (without much dressing) and it passed.

Larry 23:41, 9 Apr 2006 (EDT)