Trabalho de Conclusão de Curso
Algoritmos em sequências
Aluno: Yan Soares Couto
Orientadora: Cristina G. Fernandes
Na monografia os algoritmos são dados em pseudocódigo, aqui darei implementações destes algoritmos em C++. Todos os códigos nesta página podem ser compilados usando o comando g++ -std=c++11.
Em C++, utilizamos a classe string para representar strings, vector para representar um vetor, e map para representar uma Árvore de Busca Binária Balanceada (ABBB).
A classe string e vector são indexadas a partir de 0, então o código é ligeiramente diferente do pseudocódigo da monografia, que indexa a partir de 1.
Diferente do texto, os algoritmos implementados usam ABBBs em vez de vetores, para evitar preocupação com qual é o alfabeto usado na instância. O código continua muito similar ao discutido, e pode ser facilmente modificado.
Códigos:
Todos os arquivos possuem uma função main para testar as funções implementadas nestes. Em geral essas funções leem suas strings a partir de arquivos, e é possível usar textos bem grandes pois os algoritmos são eficientes. O site Project Gutenberg disponibiliza vários livros em formato txt que podem ser usados como strings.
Os códigos usam funções auxiliares que são implementadas de forma recursiva, e como o tamanho padrão da pilha é pequeno, para textos muito grandes este pode estourar (resultando em um Segmentation Fault). Para evitar este tipo de erro, é possível aumentar o tamanho da pilha usando ulimit em Linux (ulimit -s 100000, por exemplo), ou opções específicas de compilação (-Wl,--stack=100000, por exemplo).