Final ONI 2004: Problema B - Analisador de Textos

O problema B das finais das ONI 2004 chama-se Analisador de Textos.

Neste problema, é-nos fornecido um texto composto por L (<= 10 000) linhas de até 100 caracteres e temos de produzir uma de 4 possíveis estatísticas:

1. Calcular o número de palavras no texto e o número de palavras diferentes.
2. Contar as ocorrências de cada letra do alfabeto no texto.
3. Listar as palavras por ordem de frequência decrescente.
4. Listar as palavras por ordem de comprimento decrescente.

Não há mais de 60000 palavras no texto, nem mais de 5000 palavras diferentes. Cada palavra tem no máximo 30 letras.

Análise

Este problema é mais de implementação para o parsing do texto. Era preciso ter bastante cuidado pois os concorrentes não sabem durante a prova se as suas soluções têm bugs ou não.

Para a estatística 1, podemos usar uma Hash Table ou até uma árvore binária de pesquisa como o set da STL do C++.

A estatística 2 é a mais fácil de todas. Basta processar o texto e contar a frequência de cada letra.

Para as estatísticas 3 e 4, era necessário utilizar um algoritmo de ordenação eficiente como o Quick Sort, sendo também necessário saber ordenar por critérios diferentes.

A título de curiosidade, fui ver o código que tinha escrito para tentar resolver o problema em 2005. São 288 linhas de código horrível, incluindo a implementação de um Quick Sort à mão (eu desconhecia as várias bibliotecas do C++ à disposição) que já nem me lembro se resolve o problema a 100%.

Também tenho um código de 2008 com 140 linhas que sei que resolve o problema a 100%. Apesar de não ser tão mau, também tem muito que poderia ser melhorado.

É bom sinal olharmos para trás e vermos que o código que escrevemos era horrível. Apenas significa que nos tornamos melhores programadores.