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

using namespace std;

/*
**  The idea of this solution is sort each string with alphabet order.
**  Then each anagrams would has the same result.
**  Group the result and record the indics in orignial array, if the 
**  count is larger than 2, we find anagram.
**
**  Since the strings only contains lowercase, we could sort it with 
**  bucket sort, the time complexity if O(m), where m is length of string.
**
**  I use map for grouping, so it takes O(n log n) time, where n is size
**  of array. If we use hashtable, it could be reduced to O(n).
**  
**  Hence the total time complexity of this idea would be O(mn).
*/

string BucketSort(string s)
{
    vector<int> b(26, 0);

    for (size_t i = 0; i < s.size(); ++i)
        ++b[s[i]-'a'];
    
    s.clear();
    for (size_t i = 0; i < b.size(); ++i)
        for (size_t j = 0; j < b[i]; ++j)
            s.push_back('a' + i);

    return s;
}

vector<string> Anagrams(vector<string> &strs) 
{
    map<string, vector<size_t> > mapper;

    for (size_t i = 0; i < strs.size(); ++i)
        mapper[BucketSort(strs[i])].push_back(i);

    map<string, vector<size_t> >::iterator beg = mapper.begin();
    map<string, vector<size_t> >::iterator end = mapper.end();
    vector<string> result;
    while(beg != end)
    {
        vector<size_t>& indics = (*beg).second;
        if (indics.size() > 1)
            for (size_t i = 0; i < indics.size(); ++i)
				result.push_back(strs[indics[i]]);
        ++beg;
    }

    return result;
}


void PrintV(vector<string> &strs)
{
    for (int i = 0; i < strs.size(); ++i)
        cout << strs[i] << ", ";

    cout << endl;
}

int main(int argc, char** argv)
{
    char a[][20] = 
    {
        "amp",
        "map",
        "tea",
        "eat",
        "hello"
    };
    vector<string> strs;
    strs.assign(a, a+5);

    PrintV(strs);
	
	vector<string> result = Anagrams(strs);
	 PrintV(result);

    return 0;
}