Roteiro 8

De DCC UFMG - Maratona de Programação
Ir para: navegação, pesquisa

< Voltar para: Roteiros | Roteiro 7

Introdução

Neste roteiro, estudaremos strings. Em vários problemas, é importante saber como resolver problemas em strings como encontrar eficientemente as ocorrências de um padrão em um texto, dizer se uma palavra pertence a um dicionário, ou encontrar palíndromos em uma string. É comum, também, que problemas ad-hoc envolvam strings, ou que a entrada envolva processamento trabalhoso de strings, ou que outro tema esteja presente na solução, como Programação Dinâmica.

Há vários outros algoritmos e estruturas de dados mais avançados relacionados a strings (como Suffix Arrays e Hashing) que não serão coberto por agora, mas que você encontrará, invariavelmente, em sua carreira de competidor.

Materiais de apoio

Problemas

Lista de problemas para serem resolvidos. A solução está disponível, mas recomendamos que não a consulte antes de sofrer um pouco com o problema. Os problemas em negrito são os mais importantes. Faça-os antes de prosseguir para o próximo roteiro. Os problemas em rosa são para aquecimento.

Roteiro 8
# Problema Link Online Judge Nível Observações
0 CF50B Choosing Symbol Pairs Codeforces 1 Aquecimento
1 POODLEMG Poodle SPOJ-BR 1 Aquecimento
2 ENCOTEL Encontre o telefone SPOJ-BR 1 Aquecimento
3 UVa 11385 The Da Vinci Code UVa 2 -
4 UVa 941 Permutations UVa 2 -
5 PLAGIO Plágio SPOJ-BR 3 strings não se restringem a caracteres
6 NHAY A Needle in the Haystack SPOJ 2 -
7 PAL Palíndrome SPOJ-BR 3 -
8 FINDSR Find String Roots SPOJ 3 -
9 QUADRADO Construtor de Totens SPOJ-BR 4 lembra-se de bitmasks?
10 UVa 12526 Cellphone Typing UVa 3 -
11 UVa 10008 What's Cryptanalysis? UVa 1 toupper()

Próximo roteiro

O próximo roteiro de treinamento tratará de Geometria Computacional, um tópico também muito recorrente em competições. Recomendamos que você avance apenas depois de ler todo o material de apoio e ter feito, pelo menos, 6 problemas incluindo os 2 em negrito.

Link para o Roteiro 9

Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas