Questão de Tecnologia da Informação

Dada uma sequência de caracteres S = s1, s2, ..., sn, uma subsequência de S é dada pela remoção de zero ou mais caracteres de S. Formalmente, a sequência X = x1, x2, ..., xk é subsequência de S se existe uma sequência crescente de índices i1, ..., ik de S, tal que xj = Sij para todo j = 1, 2, ..., k. Define-se, também, um prefixo da sequência S com comprimento i para i = 0, ..., n, como Si = s1, s2, ..., si. 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 = a1, a2, ..., an e B = b1, b2, ..., bm, 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 = z1, z2, ..., zk seja uma LCS das sequências A e B. Em relação ao problema da LCS, avalie as afirmações a seguir. I. Se an = bm, então zk = an, zk = bm e Zk-1 é uma LCS de An-1 e Bm-1. II. Se an ≠ bm e zk ≠ an, então Z é uma LCS de An-1 e B. III. Seja lcs(i,j) o comprimento da LCS entre Ai e Bj. Para i, j > 0, se ai ≠ bj, então lcs(i,j) = min{lcs(i, j-1), lcs(i-1, j)}. IV. Seja lcs(i,j) o comprimento da LCS entre Ai e Bj. Para i, j > 0, se ai = bj, então lcs(i,j) = lcs(i-1,j-1)+1. É correto apenas o que se afirma em