• 1. Escrever um procedimento linear para, dadas duas cadeias de caracteres do mesmo
  comprimento n, A = a₁ a₂ ... a_n e B = b₁ b₂ ... b_n , determinar se B é uma rotação de A.
  Em outras palavras, o procedimento deve determinar se existe um valor k, 0 < k < n,
  tal que a_i = b_{[(k+i) mod n] + 1}, para todo i entre 1 e n.

  Dica: Leia a Seção 10.2 do livro de Udi Manber.

• 2. O algoritmo KMP pode ser melhorado para cadeias sobre um alfabeto binário,
  fazendo uma modificação durante a construção da tabela next, adicionando o caracter
  que não "casou" ao sufixo da parte conhecida do texto.
  Em outras palavras, você vai procurar o maior sufixo da cadeia T(i-1)c_i que casa
  com um prefixo do padrão (c_i é o complemento do caracter t_i do texto.)
  Coloque um contador de comparações, e imprima o seu valor após processar a cadeia.

• 3. Faça 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.

• 4. 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 algoritmos eficientes 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 24.maio.2000 por katia.]