MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Enunciado: Vamos considerar o problema de encontrar a Cadeia Comum mais Longa (LCS) , definindo  como LCS(A,B) a Cadeia Comum mais Longa entre as strings A e B.

Por exemplo, se considerarmos A={ALFABETO} e B={HABITAT} e os subproblemas A'={ALFA} e B'={HABI}, então podemos afirmar que:

a) LCS(A',B') + LCS(A-A',B-B') = LCS(A,B)
b) LCS(A',B') + LCS(A-A',B-B') ≠ LCS(A,B)
c) Não existe Cadeia Comum mais Longa entre os subproblemas A' e B'.
d) Só existe uma Cadeia Comum mais Longa entre A e B, ou seja, LCS(A,B) é única.
e) NDA.

Ideia original de: Lucas Miguel de Carvalho