Problema A - Finding Motifs in DNA

Autor: Arlindo Oliveira (Instituto Superior Técnico)
Tipo de problema: Strings / Dicionários
Número de ficheiros de teste: 5

Este problema tem uma inspiração bastante real, e é no fundo um clássico. A tarefa essencial do problema é conseguir guardar as subcadeias já pesquisadas, e conseguir, de modo eficiente, verificar se uma nova subcadeia já existe, aumentando o seu número de ocorrências nesse caso.

Ora, a estrutura de dados para precisamente esta tarefa tem um nome: dicionário. E existem várias implementações desta estrutura de dados, com diferentes pontos fortes e fracos, mas quase todas podiam ser usadas neste problema. Aqui ficam algumas hipóteses:

Hash Tables. Neste caso, a função de hash deveria ser bem escolhida e ter em conta a especificidade das cadeias de DNA, com apenas 4 bases azotadas.
Árvores de pesquisa balançadas, que já existem implementadas "de borla" no C++ (STL Map) e Java (TreeMap), em ambos os casos com "Red-Black Trees".
"Tries" (árvores de prefixos). Teria de ser implementada "à mão", mas não é complicada e seria muito eficiente neste caso.

Com o dicionário feito, era só adicionar a uma outra estrutura cada vez que uma subcadeia chegasse ao quorum pedido. Finalmente, era necessário ordenar por ordem lexicográfica. Mas quem não sabe ordenar com as bibliotecas da linguagem que usa? :-)

Ligações interessantes: