I think your output file has one more empty line, when I had such code I had WA1, now I'm one of the many TL12- ers :(

Also this problem can be solved with segment tree and some preprocessing:

1) create array of pairs <string word,int frequency> and sort this array

2) build segment tree on maximum on frequences of sorted array

3) answering the query:
find all words which matches the pattern - these words will be in one sequental interval because array sorted lexocographically,here example of finding this interval:
L = lower_bound(array,array+n,make_pair(pattern,-INF))-array; //substraction pointers
R = upper_bound(*,*,make_pair(pattern+"zzzzz_fill_until_max_len",+INF))-array;
now we found all relevant words, let's choose 10 most frequent:
1 most frequent word - find_max_with_segment_tree(L,R) - also should return index of maximal element
Now you should change maximal element to -INF in order to provide that second most frequent word will be founded by segment tree; change second to -INF and so on;
after answering 10 questions just undo changes: you know old values and indices of altered elements, use this this information and restore segment tree.


Edited by author 11.02.2011 08:31