• 1. Implemente uma modificação do Algoritmo Minimum_Edit_Distance, da página 158 do Manber,
  para dadas duas cadeias de caracteres A e B, de n e m caracteres, respectivamente,
  dizer qual o custo mínimo de edição e quais os passos para transformar a cadeia A na
  cadeia B com este custo.

• 2. A maior subseqüência comum de duas seqüências T e P é a maior seqüência L que é simultaneamente uma subseqüência de T e de P.
  A menor superseqüência comum de duas seqüências T e P é a menor seqüência L tal que
  ambas, T e P, são subseqüências de L.

  Escreva um programa eficiente para encontrar:

  • A maior subseqüência comum de duas seqüências T e P, e
  • A menor superseqüência comum de duas seqüências T e P.

  Dica: Leia sugestão para o problema 6.51 do livro de Udi Manber.

Retorna à página principal do curso

[Última alteração em 05.junho.2001 por katia.]