Una subsecuencia de una secuencia dada es solo la secuencia dada con algunos elementos (posiblemente ninguno o todos) omitidos. Nos dan dos secuencias X[m] e Y[n] de longitudes m y n respectivamente, con índices de X e Y a partir de 0.
Deseamos encontrar la longitud de la subsecuencia común más larga (LCS) de X[ m] e Y[n] como l(m,n), donde a continuación se proporciona una definición recursiva incompleta de la función l(i,j) para calcular la longitud del LCS de X[m] e Y[n]:
l(i,j) = 0, if either i=0 or j=0 = expr1, if i,j > 0 and X[i-1] = Y[j-1] = expr2, if i,j > 0 and X[i-1] != Y[j-1]
(A) expr1 ≡ l(i-1, j) + 1
(B) expr1 ≡ l(i, j-1)
(C) expr2 ≡ max(l(i-1, j), l(i, j- 1))
(D) expr2 ≡ max(l(i-1,j-1),l(i,j))
Respuesta: (C)
Explicación: En el problema de la subsecuencia común más larga , hay dos casos para X[0. .i] y Y[0..j]
1) The last characters of two strings match. The length of lcs is length of lcs of X[0..i-1] and Y[0..j-1] 2) The last characters don't match. The length of lcs is max of following two lcs values a) LCS of X[0..i-1] and Y[0..j] b) LCS of X[0..i] and Y[0..j-1]
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA