Anagramas V80480

Dos palabras son anagramas si tienen exactamente las mismas letras y en las mismas cantidades. Por ejemplo, eat, ate y tea son anagramas entre ellas, y también lo son listen, silent y enlist.

Haced un programa que lea una secuencia de palabras y las clasifique en grupos de anagramas. Para cada grupo, hay que escribir las palabras ordenadas alfabéticamente. Los grupos deben escribirse en un cierto orden (explicado más abajo).

Observación

En este problema el centro de interés es la eficiencia. Hay que encontrar una forma inteligente de agrupar las palabras para evitar comparaciones innecesarias.

Pista: Si ordenamos las letras de una palabra, obtenemos una especie de “signatura”. Por ejemplo, si ordenamos las letras de eat, ate y tea, obtenemos aet en los tres casos. Dos palabras son anagramas si y solo si tienen la misma signatura. Esta signatura se puede usar como clave de un map.

Para ordenar las letras de un string s, se puede usar la función sort de la librería <algorithm>:

#include <algorithm>
...
sort(s.begin(), s.end());

La salida del programa debe estar ordenada por la signatura de cada grupo, que corresponde al orden de las claves del map.

Entrada

La entrada es una secuencia de palabras (en minúsculas, sin espacios internos), una por línea, acabada por fin de entrada.

Salida

Para cada grupo de anagramas, se escribe una línea con la signatura del grupo (las letras ordenadas), seguida de : y un espacio, y a continuación las palabras del grupo ordenadas alfabéticamente y separadas por espacios. Los grupos se escriben en orden de signatura.