Impresión de la subsecuencia común más larga – Part 1

Dadas dos secuencias, imprime la subsecuencia más larga presente en ambas.

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.

Hemos discutido el problema de la subsecuencia común más larga (LCS) en una publicación anterior . La función discutida allí fue principalmente para encontrar la longitud de LCS. Para encontrar la longitud de LCS, se construyó una tabla 2D L[][]. En esta publicación, se analiza la función para construir e imprimir LCS.

A continuación se detalla el algoritmo para imprimir el LCS. Utiliza la misma tabla 2D L[][].

1. Construya L[m+1][n+1] usando los pasos discutidos en la publicación anterior .
2. El valor L[m][n] contiene la longitud de LCS. Cree una array de caracteres lcs[] de longitud igual a la longitud de lcs más 1 (uno extra para almacenar \0).
3. Atraviese la array 2D a partir de L[m][n]. Haz lo siguiente para cada celda L[i][j] 
   • Si los caracteres (en X e Y) correspondientes a L[i][j] son ​​iguales (o X[i-1] == Y[j-1]), incluya este carácter como parte de LCS. 
   • De lo contrario, compare los valores de L[i-1][j] y L[i][j-1] y vaya en la dirección del mayor valor.

La siguiente tabla (tomada de Wiki ) muestra los pasos (resaltados) seguidos por el algoritmo anterior.

A continuación se muestra la implementación del enfoque anterior. 

/* Dynamic Programming implementation of LCS problem */
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
 
/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
void lcs(char* X, char* Y, int m, int n)
{
    int L[m + 1][n + 1];
 
    /* Following steps build L[m+1][n+1] in bottom up
      fashion. Note that L[i][j] contains length of LCS of
      X[0..i-1] and Y[0..j-1] */
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                L[i][j] = 0;
            else if (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]);
        }
    }
 
    // Following code is used to print LCS
    int index = L[m][n];
 
    // Create a character array to store the lcs string
    char lcs[index + 1];
    lcs[index] = '\0'; // Set the terminating character
 
    // Start from the right-most-bottom-most corner and
    // one by one store characters in lcs[]
    int i = m, j = n;
    while (i > 0 && j > 0) {
        // If current character in X[] and Y are same, then
        // current character is part of LCS
        if (X[i - 1] == Y[j - 1]) {
            lcs[index - 1]
                = X[i - 1]; // Put current character in result
            i--;
            j--;
            index--; // reduce values of i, j and index
        }
 
        // If not same, then find the larger of two and
        // go in the direction of larger value
        else if (L[i - 1][j] > L[i][j - 1])
            i--;
        else
            j--;
    }
 
    // Print the lcs
    cout << "LCS of " << X << " and " << Y << " is " << lcs;
}
 
/* Driver program to test above function */
int main()
{
    char X[] = "AGGTAB";
    char Y[] = "GXTXAYB";
    int m = strlen(X);
    int n = strlen(Y);
    lcs(X, Y, m, n);
    return 0;
}

// Dynamic Programming implementation of LCS problem in Java
import java.io.*;
 
class LongestCommonSubsequence {
    // Returns length of LCS for X[0..m-1], Y[0..n-1]
    static void lcs(String X, String Y, int m, int n)
    {
        int[][] L = new int[m + 1][n + 1];
 
        // Following steps build L[m+1][n+1] in bottom up
        // fashion. Note that L[i][j] contains length of LCS
        // of X[0..i-1] and Y[0..j-1]
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 || j == 0)
                    L[i][j] = 0;
                else if (X.charAt(i - 1) == Y.charAt(j - 1))
                    L[i][j] = L[i - 1][j - 1] + 1;
                else
                    L[i][j] = Math.max(L[i - 1][j],
                                       L[i][j - 1]);
            }
        }
 
        // Following code is used to print LCS
        int index = L[m][n];
        int temp = index;
 
        // Create a character array to store the lcs string
        char[] lcs = new char[index + 1];
        lcs[index]
            = '\u0000'; // Set the terminating character
 
        // Start from the right-most-bottom-most corner and
        // one by one store characters in lcs[]
        int i = m;
        int j = n;
        while (i > 0 && j > 0) {
            // If current character in X[] and Y are same,
            // then current character is part of LCS
            if (X.charAt(i - 1) == Y.charAt(j - 1)) {
                // Put current character in result
                lcs[index - 1] = X.charAt(i - 1);
 
                // reduce values of i, j and index
                i--;
                j--;
                index--;
            }
 
            // If not same, then find the larger of two and
            // go in the direction of larger value
            else if (L[i - 1][j] > L[i][j - 1])
                i--;
            else
                j--;
        }
 
        // Print the lcs
        System.out.print("LCS of " + X + " and " + Y
                         + " is ");
        for (int k = 0; k <= temp; k++)
            System.out.print(lcs[k]);
    }
 
    // driver program
    public static void main(String[] args)
    {
        String X = "AGGTAB";
        String Y = "GXTXAYB";
        int m = X.length();
        int n = Y.length();
        lcs(X, Y, m, n);
    }
}
 
// Contributed by Pramod Kumar

# Dynamic programming implementation of LCS problem
 
# Returns length of LCS for X[0..m-1], Y[0..n-1]
 
 
def lcs(X, Y, m, n):
    L = [[0 for i in range(n+1)] for j in range(m+1)]
 
    # Following steps build L[m+1][n+1] in bottom up fashion. Note
    # that 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])
 
        # Create a string variable to store the lcs string
    lcs = ""
 
    # Start from the right-most-bottom-most corner and
    # one by one store characters in lcs[]
    i = m
    j = n
    while i > 0 and j > 0:
 
        # If current character in X[] and Y are same, then
        # current character is part of LCS
        if X[i-1] == Y[j-1]:
            lcs += X[i-1]
            i -= 1
            j -= 1
 
        # If not same, then find the larger of two and
        # go in the direction of larger value
        elif L[i-1][j] > L[i][j-1]:
            i -= 1
             
        else:
            j -= 1
 
    # We traversed the table in reverse order
    # LCS is the reverse of what we got
    lcs = lcs[::-1]
    print("LCS of " + X + " and " + Y + " is " + lcs)
 
 
# Driver program
X = "AGGTAB"
Y = "GXTXAYB"
m = len(X)
n = len(Y)
lcs(X, Y, m, n)
 
# This code is contributed by AMAN ASATI

// Dynamic Programming implementation
// of LCS problem in C#
using System;
 
class GFG {
    // Returns length of LCS for X[0..m-1], Y[0..n-1]
    static void lcs(String X, String Y, int m, int n)
    {
        int[, ] L = new int[m + 1, n + 1];
 
        // Following steps build L[m+1][n+1] in
        // bottom up fashion. Note that L[i][j]
        // contains length of LCS of X[0..i-1]
        // and Y[0..j-1]
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 || j == 0)
                    L[i, j] = 0;
                else if (X[i - 1] == Y[j - 1])
                    L[i, j] = L[i - 1, j - 1] + 1;
                else
                    L[i, j] = Math.Max(L[i - 1, j],
                                       L[i, j - 1]);
            }
        }
 
        // Following code is used to print LCS
        int index = L[m, n];
        int temp = index;
 
        // Create a character array
        // to store the lcs string
        char[] lcs = new char[index + 1];
 
        // Set the terminating character
        lcs[index] = '\0';
 
        // Start from the right-most-bottom-most corner
        // and one by one store characters in lcs[]
        int k = m, l = n;
        while (k > 0 && l > 0) {
            // If current character in X[] and Y
            // are same, then current character
            // is part of LCS
            if (X[k - 1] == Y[l - 1]) {
                // Put current character in result
                lcs[index - 1] = X[k - 1];
 
                // reduce values of i, j and index
                k--;
                l--;
                index--;
            }
 
            // If not same, then find the larger of two and
            // go in the direction of larger value
            else if (L[k - 1, l] > L[k, l - 1])
                k--;
            else
                l--;
        }
 
        // Print the lcs
        Console.Write("LCS of " + X + " and " + Y + " is ");
        for (int q = 0; q <= temp; q++)
            Console.Write(lcs[q]);
    }
 
    // Driver program
    public static void Main()
    {
        String X = "AGGTAB";
        String Y = "GXTXAYB";
        int m = X.Length;
        int n = Y.Length;
        lcs(X, Y, m, n);
    }
}
 
// This code is contributed by Sam007

<?php
// Dynamic Programming implementation of LCS problem
 
// Returns length of LCS for X[0..m-1], Y[0..n-1]
function lcs( $X, $Y, $m, $n )
{
    $L = array_fill(0, $m + 1,
         array_fill(0, $n + 1, NULL));
     
    /* Following steps build L[m+1][n+1] in bottom
       up fashion. Note that L[i][j] contains length
       of LCS of X[0..i-1] and Y[0..j-1] */
    for ($i = 0; $i <= $m; $i++)
    {
        for ($j = 0; $j <= $n; $j++)
        {
            if ($i == 0 || $j == 0)
                $L[$i][$j] = 0;
            else if ($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]);
        }
    }
     
    // Following code is used to print LCS
    $index = $L[$m][$n];
    $temp = $index;
     
    // Create a character array to store the lcs string
    $lcs = array_fill(0, $index + 1, NULL);
    $lcs[$index] = ''; // Set the terminating character
     
    // Start from the right-most-bottom-most corner
    // and one by one store characters in lcs[]
    $i = $m;
    $j = $n;
    while ($i > 0 && $j > 0)
    {
        // If current character in X[] and Y are same,
        // then current character is part of LCS
        if ($X[$i - 1] == $Y[$j - 1])
        {
            // Put current character in result
            $lcs[$index - 1] = $X[$i - 1];
            $i--;
            $j--;
            $index--;    // reduce values of i, j and index
        }
     
        // If not same, then find the larger of two
        // and go in the direction of larger value
        else if ($L[$i - 1][$j] > $L[$i][$j - 1])
            $i--;
        else
            $j--;
    }
     
    // Print the lcs
    echo "LCS of " . $X . " and " . $Y . " is ";
    for($k = 0; $k < $temp; $k++)
        echo $lcs[$k];
}
 
// Driver Code
$X = "AGGTAB";
$Y = "GXTXAYB";
$m = strlen($X);
$n = strlen($Y);
lcs($X, $Y, $m, $n);
 
// This code is contributed by ita_c
?>

<script>
function ReverseString(str) {
   return str.split('').reverse().join('')
}
   
function max(a, b)
{
    if (a > b)
        return a;
    else
        return b;
}
function printLCS(str1, str2) {
    var len1 = str1.length;
    var len2 = str2.length;
    var lcs = new Array(len1 + 1);
    for (var i = 0; i <= len1; i++) {
        lcs[i] = new Array(len2 + 1)
    }
    for (var i = 0; i <= len1; i++) {
        for (var j = 0; j <= len2; j++) {
            if (i == 0 || j == 0) {
                lcs[i][j] = 0;
            }
            else {
                if (str1[i - 1] == str2[j - 1]) {
                    lcs[i][j] = 1 + lcs[i - 1][j - 1];
                }
                else {
                    lcs[i][j] = max(lcs[i][j - 1], lcs[i - 1][j]);
                }
            }
        }}
        
        var n = lcs[len1][len2];
         document.write("Length of common subsequence is: " +
         n + "<br>" + "The subsequence is : ");
        var str="";
       var i = len1;
       var j = len2;
       while(i>0&&j>0)
       {
            if(str1[i - 1] == str2[j - 1])
            {
                str += str1[i - 1];
                i--;
                j--;
            }
            else{
            if(lcs[i][j-1]>lcs[i-1][j])
            {
                j--;
            }
            else
            {
                i--;
            }
            }
        }
       return ReverseString(str);
    }
    var str1 = "AGGTAB";
    var str2 = "GXTXAYB";
    document.write(printLCS(str1, str2));
     
    // This code is contributed by akshitsaxenaa09
</script>

LCS of AGGTAB and GXTXAYB is GTAB

Tiempo Complejidad: O(m*n)
Espacio Auxiliar: O(m*n)