Considere dos strings A = «qpqrr» y B = «pqprqrp». Sea x la longitud de la subsecuencia común más larga (no necesariamente contigua) entre A y B y sea y el número de tales subsecuencias comunes más largas entre A y B. Entonces x + 10y = ___.
(A) 33
(B) 23
(C) 43
(D) 34
Respuesta: (D)
Explicación: //El LCS es de longitud 4. Hay 3 LCS de longitud 4 “qprr”, “pqrr” y qpqr
Una subsecuencia es una secuencia que se puede derivar de otra secuencia seleccionando cero o más elementos de ella, sin cambiar el orden de los elementos restantes. La subsecuencia no necesita ser contigua. Dado que la longitud de las strings dadas A = «qpqrr» y B = «pqprqrp» es muy pequeña, no necesitamos construir una array de 5 × 7 y resolverla usando programación dinámica. Más bien podemos resolverlo manualmente solo por fuerza bruta. Primero comprobaremos si existe una subsecuencia de longitud 5 ya que min_length(A,B) = 5.
Como no hay subsecuencia, ahora comprobaremos la longitud 4. “qprr”, “pqrr” y “qpqr” son comunes en ambas strings.
X = 4 y Y = 3
X + 10Y = 34
Esta solución es aportada por Pranjul Ahuja
Cuestionario de esta pregunta
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