ONI 2003 - Alcunhas

O segundo problema das finais das ONI 2003 chama-se Alcunhas. Neste problema, temos um dicionário com N palavras (N <= 1000) com até 30 letras. Posto isto, é dado um número indeterminado de nomes de pessoas na mesma linha separados por espaços e temos de terminar quais os nomes cujas iniciais formam palavras do dicionário. Exemplo: as iniciais de "Rita Inês Costa Almeida" formam a palavra "rica".

Análise

Mais uma vez, convém ter em conta que estamos em 2003 e que as linguagens de programação permitidas são Pascal, C e C++, sendo que duvido que alguém usasse a STL do C++ (que facilita neste problema).

A base do problema consiste no problema (agora clássico) de procura de palavras num dicionário. Este dicionário não é particularmente grande, mas uma pesquisa em O(N) certamente que não chega para os 100 pontos.

Com este limite de 1000 palavras, podemos adoptar várias abordagens:

• Colocar as palavras num array de strings, ordenar o array de strings e utilizar pesquisa binária para procurar as palavras no dicionário. A ordenação seria O(N log N) e cada pesquisa binária O(log N).
• Colocar as palavras num set da STL do C++. A pesquisa num set demora O(log N) mas seria provavelmente suficiente neste problema.
• Colocar as palavras numa Hash Table. A pesquisa em O(1) na hash table seria certamente eficiente. Nota: o C++11 adicionou a classe unordered_set que é uma Hash Table.
• Colocar as palavras numa Trie. A pesquisa numa Trie é proporcional ao tamanho da palavra, sendo muito eficiente.

Um pormenor importante é a ordenação do resultado que poderia ser fonte de erros. Mas visto que é garantido que existem no máximo 500 nomes no resultado, até um algoritmo de ordenação O(N²) deveria ser suficiente.

Embora seja desnecessário, já que nos é garantido que os nomes têm no máximo 10 palavras, podemos ignorar todas as palavras do dicionário com mais de 10 letras.