Qualificação ONI 2005: Problema C - Descobrindo Anagramas

O último problema da qualificação das ONI 2005 chama-se Descobrindo Anagramas.

Uma classe de anagramas é um conjunto de palavras com as mesmas letras mas por outra ordem. Exemplo: caras, casar e sacar são anagramas, fio e foi formam outra classe.

Dado um texto com no máximo 20 000 palavras distintas, pretende-se saber quantas classes de anagramas existem.

Nos dias de hoje, esta este problema muito frequente em entrevistas de emprego.


Análise

É importante notar que o limite de 20 000 apenas se refere ao número de palavras distintas, por isso, o número total de palavras no texto pode ser muito superior.

Uma forma simples para ver se 2 palavras são anagramas é ordenar os seus caracteres e ver se as palavras são iguais depois da ordenação. Assim, uma classe de anagramas pode ser identificada pelas suas letras ordenadas: aacrs e fio para os exemplos dados. Como as palavras só têm até 30 letras, a eficiência da ordenação não é significativa.

Para cada palavra no texto, temos de verificar se a palavra é anagrama de uma palavra diferente vista anteriormente. Se uma palavra aparecer múltiplas vezes no texto, não forma uma classe de anagramas.

Visto que o número de palavras é bastante elevado (provavelmente 100 000+), necessitamos de pesquisar se uma classe de anagrama já ocorreu anteriormente de forma bastante eficiente.
Como já tenho referido noutros posts, os métodos de eleição para este tipo de pesquisas são as Hash Tables e as Tries.

Volto a relembrar que estamos em 2005, por isso a classe unordered_set da STL do C++ não existia. Se bem me lembro, o set não chegava para passar no tempo limite, por isso, a opção mais simples em Pascal ou C/C++ de 2005 é o uso de uma Trie. A Trie tem a desvantagem do consumo de memória, mas neste caso não deve ter problemas com 20 000 palavras distintas com tamanho até 30 letras.

No meu caso, penso que desconhecia as Tries quando tentei resolver o problema novamente em 2006 ou 2007 e implementei uma Hash Table simples que suporta apenas inserção e pesquisa. Note-se que é um código +- minimizado para levar na biblioteca de algoritmos para os concursos.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

const int HASH_SIZE = 240007; // Numero primo! struct TYPE { char key[51]; // string, número, o que for char used; bool operator == (TYPE& t) { return strcmp(key, t.key ) == 0; } } hash[HASH_SIZE]; inline int hash_function(TYPE& s) { unsigned int key=0; for (int i=0; s.key[i] ; i++) key = key * 37 + s.key[i]; // ignora overflows return key % HASH_SIZE; } inline void insert(TYPE &s) { // resolução de colisões com pesquisa linear int key = hash_function(s); // assumindo que nao ha repetidos while (hash[key].used) if (++key == HASH_SIZE) key=0; memcpy(&hash[key], &s, sizeof(TYPE)); hash[key].used = 1; } inline bool find(TYPE& s) { int key = hash_function(s); bool found = s == hash[key] && hash[key].used; for (++key; hash[key].used && !found; found = s == hash[key++]) if (key==HASH_SIZE) key=0; return found; }