MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-033

Enunciado: Considere o problema de encontrar a Subcadeia Comum mais Longa (LCS), definindo como LCS(A,B) o tamanho da subcadeia comum mais longa entre as strings A e B. Tomando A="ALFABETO" e B="HABITAT" e o subproblema A'="ALFA" e B'="HABI", podemos afirmar que:

a) LCS(A',B') + LCS(A-A',B-B') = LCS(A,B) - 1
b) LCS(A',B') + LCS(A-A',B-B') = LCS(A,B)
c) LCS(A',B') + LCS(A-A',B-B') = LCS(A,B) + 1
d) LCS(A',B') + LCS(A-A',B-B') = LCS(A,B) + 2
e) NDA.

Ideia original de: Lucas Miguel de Carvalho