Este enunciado ha sido evaluado por expertos así se asegura la exactitud de esta reseña.
Solución:
Hay 2 problemas principales con su código que hacen que el algoritmo genere una respuesta incorrecta.
if i == 0 or j == 0 en la linea 16
Solo siguiendo el video muestra que esta línea no tiene sentido cuando s1[1] != s2[j]porque la subsecuencia común más larga de “ab” y “a” tiene una longitud de 1 aunque su algoritmo establece matrix[0][1] = 0 para este ejemplo. Por lo tanto, debe eliminar esta declaración if. Mientras estás en eso, tienes que considerar qué max(matrix[i-1][j], matrix[i][j-1]) hace por i == 0 o j == 0. Ahora hay dos enfoques diferentes:
-
El explícito:
max(matrix[i-1][j] if i != 0 else 0, matrix[i][j-1] if j != 0 else 0) -
El implícito:
max(matrix[i-1][j], matrix[i][j-1])Este funciona, porque en Python se usan índices negativos para obtener el último elemento de una lista y estos elementos son 0 en este caso.
cs += s1[i] en línea 11/14
Por ejemplo, si encontró que la subsecuencia común más larga de “a” y “abcd” es “a”, su algoritmo establece la subsecuencia común más larga para “a” y “abcda” como “aa”, lo cual no tiene sentido. estoy luchando por explicar por qué no funciona así, así que le sugiero que mire algunos ejemplos, tal vez usando http://pythontutor.com/visualize.html
Solución
Para abordar ambos problemas, puede usar la matriz para almacenar la subsecuencia común más larga que encontró para los problemas más pequeños. Terminas con esto:
def lcs(s1, s2):
matrix = [["" for x in range(len(s2))] for x in range(len(s1))]
for i in range(len(s1)):
for j in range(len(s2)):
if s1[i] == s2[j]:
if i == 0 or j == 0:
matrix[i][j] = s1[i]
else:
matrix[i][j] = matrix[i-1][j-1] + s1[i]
else:
matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1], key=len)
cs = matrix[-1][-1]
return len(cs), cs
print(lcs("abcdaf", "acbcf"))
Esta implementación específica solo devuelve un resultado posible. Puede intentar implementar un algoritmo que proporcione todas las secuencias comunes más largas como ejercicio. Tal vez eche un vistazo a la página de Wikipedia como lo sugiere גלעד ברקן
¿Cuánto tiempo lleva “entender” por qué su código no funciona?
Obviamente no hay una respuesta clara. Siempre ayuda pensar en ejemplos y, en el caso de los algoritmos, Wikipedia suele tener un buen pseudocódigo en el que puede basar sus implementaciones. Cuando esté familiarizado con los conceptos y las estructuras de datos involucradas en el algoritmo, debería poder implementarlo en un día, diría yo (pero definitivamente no soy un experto). En general, la búsqueda de errores lógicos en su código puede llevar varios días, según el tamaño del código. Para practicar este tipo de pensamiento estructurado, algorítmico y matemático, recomiendo encarecidamente projecteuler.net.
Para aquellos que buscan una solución integrada:
from difflib import SequenceMatcher
str_a = "xBCDxFGxxxKLMx"
str_b = "aBCDeFGhijKLMn"
s = SequenceMatcher(None, str_a, str_b)
lcs = ''.join([str_a[block.a:(block.a + block.size)] for block in s.get_matching_blocks()])
# lcs = 'BCDFGKLM'