Subsecuencia común más larga en Python
- Use el método Naive para encontrar la subsecuencia común más larga en Python
- Use la programación dinámica para encontrar la subsecuencia común más larga en Python
Una subsecuencia es una secuencia obtenida de las secuencias dadas después de eliminar algunos o ningún carácter sin cambiar el orden de los caracteres restantes. La subsecuencia común más larga significa la subsecuencia más larga común a todas las secuencias dadas.
Este tutorial te enseñará a encontrar la longitud de la subsecuencia común más larga entre dos secuencias en Python.
Use el método Naive para encontrar la subsecuencia común más larga en Python
Considere que tenemos dos secuencias: S1 y S2, donde:
S1 = QEREW
S2 = QWRE
Aquí, las subsecuencias comunes son QE, QW, QR, QRE y RE. Entre estas, la subsecuencia común más larga es QRE, y su longitud es 3.
Ahora, veamos la solución de Python para imprimir la longitud de la subsecuencia común más larga.
Código:
def LCS(S1, S2, x, y):
if x == 0 or y == 0:
return 0
if S1[x - 1] == S2[y - 1]:
return LCS(S1, S2, x - 1, y - 1) + 1
return max(LCS(S1, S2, x, y - 1), LCS(S1, S2, x - 1, y))
S1 = "QEREW"
S2 = "QWRE"
x = len(S1)
y = len(S2)
print("Length of LCS is", LCS(S1, S2, x, y))
Producción :
Length of LCS is 3
Este método es un enfoque recursivo para resolver el problema LCS en Python. Comprueba todas las subsecuencias posibles de secuencias dadas y encuentra la subsecuencia común más larga.
Use la programación dinámica para encontrar la subsecuencia común más larga en Python
La programación dinámica es la optimización del método de recursividad simple. Como podemos ver, hay subproblemas superpuestos en el enfoque recursivo, con muchas llamadas de funciones repetidas.
El enfoque dinámico guarda el resultado de cada llamada de función en una matriz para que pueda usarse cuando sea necesario. Como resultado, reduce el número de llamadas a funciones.
Código:
def LCS(S1, S2, m, n):
R = [[None] * (n + 1) for i in range(m + 1)]
for i in range(m + 1):
for j in range(n + 1):
if i == 0 or j == 0:
R[i][j] = 0
elif S1[i - 1] == S2[j - 1]:
R[i][j] = R[i - 1][j - 1] + 1
else:
R[i][j] = max(R[i - 1][j], R[i][j - 1])
return R[m][n]
S1 = "QEREW"
S2 = "QWRE"
m = len(S1)
n = len(S2)
print("Length of LCS is", LCS(S1, S2, m, n))
Producción :
Length of LCS is 3
Este método es más rápido y eficiente ya que tiene una complejidad temporal de O(mn).
