Tópicos Especiais em Programação - Strings (2024.2)

📚 Sobre a Disciplina

Esta disciplina, ministrada pelo professor Edson Alves da Costa Junior, é focada em programação competitiva, abordando algoritmos e estruturas de dados relacionados a strings. Ao longo do semestre, realizamos uma série de listas de exercícios, cujas resoluções estão disponíveis neste repositório.

Além de reforçar conceitos sobre strings, aproveitei a oportunidade para aprofundar meus conhecimentos em C++ e utilizar suas bibliotecas e funcionalidades avançadas.

🗂 Estrutura do Conteúdo

📌 Lista 0: Exercícios Preparatórios

Lista introdutória com problemas para revisão e aquecimento.

📌 Lista 1: Definição e Representação de Strings

• Conceitos fundamentais sobre strings.
• Modelos de representação e manipulação em diferentes linguagens.

📌 Lista 2: Algoritmos Elementares

• Palíndromos: Verificação e construção de palíndromos.
• Histograma: Contagem de caracteres e análise de frequência.
• Tokenização: Divisão de strings em palavras ou símbolos.
• Programação Funcional: Manipulação de strings usando funções de ordem superior.
• Anagramas: Identificação e geração de anagramas.
• Expressões Regulares: Uso de regex para manipulação e validação de strings.

📌 Lista 3: Busca em Strings

• Definição de busca em strings: Conceitos e abordagens gerais.
• Hashes: Funções de hash aplicadas a strings.
• Algoritmo de Rabin-Karp: Busca eficiente baseada em hashing.
• KMP (Knuth-Morris-Pratt): Algoritmo para busca exata em tempo linear.
• Z-Function: Técnica avançada para padrões em strings.

🛠 Algoritmos de Busca na STL

• Métodos da classe string: Funções essenciais para manipulação de strings em C++.
• Métodos da STL: Uso de algoritmos e estruturas da Standard Template Library.
• Introdução à Programação Dinâmica: Aplicando PD para otimização de problemas envolvendo strings.

🎯 Strings e Programação Dinâmica

• Edit Distance: Cálculo da menor quantidade de operações para transformar uma string em outra.
• Maior Subsequência Comum (LCS): Encontrar a subsequência comum mais longa entre duas strings.
• Maior Subsequência Palíndroma: Determinar a maior subsequência que é um palíndromo.

🌳 Tries

• Definição: Estrutura de dados eficiente para manipulação de strings.
• Implementação Naive: Construção básica de uma trie.
• Implementação com Memória Linear: Otimização para reduzir o uso de memória.

🚀 Como Usar Este Repositório

Cada lista de exercícios tem uma pasta correspondente contendo:

• Problemas resolvidos com código-fonte em C++.
• Explicações e análises de complexidade.
• Referências adicionais para estudo complementar.

📜 Licença

Este projeto está licenciado sob a Licença MIT - veja o arquivo LICENSE para mais detalhes.