Questão 2931152

Dada uma sequência de caracteres S = s₁, s₂, ..., sₙ, uma subsequência de S é dada pela remoção de zero ou mais caracteres de S. Formalmente, a sequência X = x₁, x₂, ..., xₖ é subsequência de S se existe uma sequência crescente de índices i₁, ..., iₖ de S, tal que xⱼ = sᵢⱼ para todo j = 1, 2, ..., k. Define-se, também, um prefixo da sequência S com comprimento i para i = 0, ..., n, como Sᵢ = s₁, s₂, ..., sᵢ.

O problema da Subsequência Comum Mais Longa (LCS) e suas variações, definido a seguir, pode ser utilizado em análise de textos e em bioinformática. O problema da LCS pressupõe duas sequências de caracteres

A = a₁, a₂, ..., aₙ e B = b₁, b₂, ..., bₘ de comprimentos n e m, respectivamente.

Dadas essas duas sequências, é preciso encontrar uma sequência de maior comprimento possível que seja, simultaneamente, subsequência de A e de B.

A partir dessas informações, considere que Z = z₁, z₂, ..., zₖ seja uma LCS das sequências A e B.

Em relação ao problema da LCS, avalie as afirmações a seguir:

I. Se aₙ = bₘ, então zₖ = aₙ = bₘ = Zₖ é uma LCS de Aₙ₋₁ e Bₘ₋₁.

II. Se aₙ ≠ bₘ e zₖ = aₙ, então Z é uma LCS de Aₙ₋₁ e Bₘ.

III. Seja lcs(i,j) o comprimento da LCS entre Aᵢ e Bⱼ. Para i, j > 0, se aᵢ ≠ bⱼ, então lcs(i,j) = min{lcs(i, j-1), lcs(i-1, j)}.

IV. Seja lcs(i,j) o comprimento da LCS entre Aᵢ e Bⱼ. Para i, j > 0, se aᵢ = bⱼ, então lcs(i,j) = lcs(i-1, j-1) + 1.