Programa de Python para la subsecuencia común más larga

Declaración del problema de LCS: dadas dos secuencias, encuentre la longitud de la subsecuencia más larga presente en ambas. Una subsecuencia es una secuencia que aparece en el mismo orden relativo, pero no necesariamente contigua. Por ejemplo, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc son subsecuencias de “abcdefg”. Entonces, una string de longitud n tiene 2^n posibles subsecuencias diferentes. Es un problema clásico de informática, la base de diff (un programa de comparación de archivos que genera las diferencias entre dos archivos) y tiene aplicaciones en bioinformática. Ejemplos:LCS para las secuencias de entrada «ABCDGH» y «AEDFHR» es «ADH» de longitud 3. LCS para las secuencias de entrada «AGGTAB» y «GXTXAYB» es «GTAB» de longitud 4. Deje que las secuencias de entrada sean X[0..m- 1] y Y[0..n-1] de longitudes m y n respectivamente. Y sea L(X[0..m-1], Y[0..n-1]) la longitud de LCS de las dos secuencias X e Y. A continuación se muestra la definición recursiva de L(X[0.. m-1], Y[0..n-1]). Si los últimos caracteres de ambas secuencias coinciden (o X[m-1] == Y[n-1]), entonces L(X[0..m-1], Y[0..n-1]) = 1 + L(X[0..m-2], Y[0..n-2]) Si los últimos caracteres de ambas secuencias no coinciden (o X[m-1] != Y[n-1]), entonces L (X[0..m-1], Y[0..n-1]) = MÁX (L(X[0..m-2], Y[0..n-1]), L(X [0..m-1], Y[0..n-2]) 

# A Naive recursive Python implementation of LCS problem
 
def lcs(X, Y, m, n):
 
    if m == 0 or n == 0:
       return 0;
    elif X[m-1] == Y[n-1]:
       return 1 + lcs(X, Y, m-1, n-1);
    else:
       return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
 
 
# Driver program to test the above function
X = "AGGTAB"
Y = "GXTXAYB"
print ("Length of LCS is ", lcs(X, Y, len(X), len(Y)))

Length of LCS is  4

Complejidad de tiempo : O(2 ⁿ )

Espacio Auxiliar: O(n)

A continuación se muestra una implementación tabulada para el problema LCS. 

# Dynamic Programming implementation of LCS problem
 
def lcs(X, Y):
    # find the length of the strings
    m = len(X)
    n = len(Y)
 
    # declaring the array for storing the dp values
    L = [[None]*(n + 1) for i in range(m + 1)]
 
    """Following steps build L[m + 1][n + 1] in bottom up fashion
    Note: L[i][j] contains length of LCS of X[0..i-1]
    and Y[0..j-1]"""
    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0 or j == 0 :
                L[i][j] = 0
            elif X[i-1] == Y[j-1]:
                L[i][j] = L[i-1][j-1]+1
            else:
                L[i][j] = max(L[i-1][j], L[i][j-1])
 
    # L[m][n] contains the length of LCS of X[0..n-1] & Y[0..m-1]
    return L[m][n]
# end of function lcs
 
 
# Driver program to test the above function
X = "AGGTAB"
Y = "GXTXAYB"
print("Length of LCS is ", lcs(X, Y))
 
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

Length of LCS is  4

Complejidad del tiempo : O(n*m)

Espacio Auxiliar: O(n*m)

Consulte el artículo completo sobre programación dinámica | ¡ Establezca 4 (Subsecuencia común más larga) para obtener más detalles!