INEP, ENADE

Dada uma sequência de caracteres S = s , s , ..., s , uma subsequência de S é dada pela 1 2 n remoção de zero ou mais caracteres de S. Formalmente, a sequência X = x , x , ..., x é 1 2 k subsequência de S se existe uma sequência crescente de índices i , ..., i de S, tal que x = S 1 k j ij 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 .

i 1 2 i 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. 1 2 n 1 2 m 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. 1 2 k Em relação ao problema da LCS, avalie as afirmações a seguir.

1. I. Se a = b , então z = a , z = b e Z é uma LCS de A e B . n m k n k m k-1 n-1 m-1
2. II. Se a ≠ b e z ≠ a , então Z é uma LCS de A e B. n m k n n-1
3. III. Seja lcs(i,j) o comprimento da LCS entre A e B . Para i, j > 0, se a ≠ b , então i j i j lcs(i,j) = min{lcs(i, j-1), lcs(i-1, j)}.
4. IV. Seja lcs(i,j) o comprimento da LCS entre A e B . Para i, j > 0, se a = b , então i j i j lcs(i,j) = lcs(i-1,j-1)+1.

É correto apenas o que se afirma em