XXVI Olimpíada Brasileira de Informática

Distância entre palavras

Vamos definir três tipos de operações básicas:
  • inserir uma letra em uma palavra;
  • remover uma letra de uma palavra;
  • substituir um letra de uma palavra.
Definimos também a distância entre duas palavras como o número mínimo de operações básicas para transformar a primeira palavra na segunda. Por exemplo, a distância entre as palavras maria e clara é 3:
  1. remover a letra i: maria→ mara
  2. substituir a letra m pela letra c: mara→ cara
  3. inserir a letra l: cara→ clara

Questão 1. Qual a distância entre poesia e poema?
1
2
3
4
5

Questão 2. Qual a distância entre pescada e escala?
1
2
3
4
5

Tarefas Iniciação Nível Júnior
Promoção
logo sbc
Patrocínio
Apoio
Coordenação