Subsecuencia común más larga | DP usando Memoización

Dadas dos strings s1 y s2, la tarea es encontrar la longitud de la subsecuencia común más larga presente en ambas.

Ejemplos:  

Entrada: s1 = “ABCDGH”, s2 = “AEDFHR” 
Salida:
LCS para las Secuencias de entrada “AGGTAB” y “GXTXAYB” es “GTAB” de longitud 4.
Entrada: s1 = “striver”, s2 = “raj” 
Salida: 1  

La solución ingenua para este problema es generar todas las subsecuencias de ambas secuencias dadas y encontrar la subsecuencia coincidente más larga. Esta solución es exponencial en términos de complejidad temporal. La solución recursiva general del problema es generar todas las subsecuencias de ambas secuencias dadas y encontrar la subsecuencia coincidente más larga. El total de combinaciones posibles será 2 n . Por lo tanto, la solución recursiva tomará O(2 n )
Subestructura óptima: 

  • Deje que las secuencias de entrada sean X[0…m-1] e 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]) = MAX ( L(X[0…m-2], Y[0…n-1]), L(X[0…m-1], Y[0…n-2])

A continuación se muestra la solución recursiva al problema LCS: 

C++

// A Naive C++ recursive implementation
// of LCS of two strings
#include <bits/stdc++.h>
using namespace std;
 
// Returns length of LCS for X[0..m-1], Y[0..n-1]
int lcs(string X, string Y, int m, int n)
{
    if (m == 0 || n == 0)
        return 0;
 
    if (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 Code
int main()
{
    string X = "AGGTAB";
    string Y = "GXTXAYB";
 
    // Find the length of string
    int m = X.length();
    int n = Y.length();
 
    cout << "Length of LCS: " << lcs(X, Y, m, n);
 
    return 0;
}

Java

// A Naive Java recursive implementation
// of LCS of two strings
 
class GFG {
 
// Returns length of LCS for X[0..m-1], Y[0..n-1]
    static int lcs(String X, String Y, int m, int n) {
        if (m == 0 || n == 0) {
            return 0;
        }
 
        if (X.charAt(m - 1) == Y.charAt(n - 1)) {
            return 1 + lcs(X, Y, m - 1, n - 1);
        } else {
            return Math.max(lcs(X, Y, m, n - 1),
                    lcs(X, Y, m - 1, n));
        }
    }
// Driver Code
 
    public static void main(String[] args) {
        String X = "AGGTAB";
        String Y = "GXTXAYB";
 
        // Find the length of String
        int m = X.length();
        int n = Y.length();
        System.out.println("Length of LCS: " + lcs(X, Y, m, n));
 
    }
}
 
// This code is contributed by 29AjayKumar

Python3

# A Naive Python recursive implementation
# of LCS of two strings
 
# Returns length of LCS for X[0..m-1], Y[0..n-1]
def lcs(X, Y, m, n):
    if (m == 0 or n == 0):
        return 0
 
    if (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 Code
if __name__ == '__main__':
    X = "AGGTAB"
    Y = "GXTXAYB"
 
    # Find the length of string
    m = len(X)
    n = len(Y)
 
    print("Length of LCS:",
           lcs(X, Y, m, n))
 
# This code is contributed by 29AjayKumar

C#

// A Naive recursive C#implementation of
// LCS of two strings
using System;
 
class GFG
{
 
// Returns length of LCS for
// X[0..m-1], Y[0..n-1]
static int lcs(String X, String Y,
               int m, int n)
{
    if (m == 0 || n == 0)
    {
        return 0;
    }
 
    if (X[m - 1] == Y[n - 1])
    {
        return 1 + lcs(X, Y, m - 1, n - 1);
    } else {
        return Math.Max(lcs(X, Y, m, n - 1),
                        lcs(X, Y, m - 1, n));
    }
}
 
// Driver Code
public static void Main()
{
    String X = "AGGTAB";
    String Y = "GXTXAYB";
 
    // Find the length of String
    int m = X.Length;
    int n = Y.Length;
    Console.Write("Length of LCS: " +
                    lcs(X, Y, m, n));
}
}
 
// This code is contributed by 29AjayKumar

PHP

<?php
// A Naive PHP recursive implementation
// of LCS of two strings
 
// Returns length of LCS for
// X[0..m-1], Y[0..n-1]
function lcs($X, $Y, $m, $n)
{
    if ($m == 0 || $n == 0)
        return 0;
 
    if ($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 Code
$X = "AGGTAB";
$Y = "GXTXAYB";
 
// Find the length of string
$m = strlen($X);
$n = strlen($Y);
 
echo "Length of LCS: " . lcs($X, $Y, $m, $n);
 
// This code is contributed by ita_c
?>

Javascript

<script>
// A Naive Javascript recursive implementation
// of LCS of two strings
     
    // Returns length of LCS for X[0..m-1], Y[0..n-1]
    function lcs(X,Y,m,n)
    {
        if (m == 0 || n == 0) {
            return 0;
        }
   
        if (X[m-1] == Y[n-1]) {
            return 1 + lcs(X, Y, m - 1, n - 1);
        } else {
            return Math.max(lcs(X, Y, m, n - 1),
                    lcs(X, Y, m - 1, n));
        }
    }
     
    // Driver Code
    let X = "AGGTAB";
    let Y = "GXTXAYB";
    // Find the length of String
    let m = X.length;
    let n = Y.length;
    document.write("Length of LCS: " + lcs(X, Y, m, n));
 
 
// This code is contributed by rag2127
</script>
Producción: 

Length of LCS: 4

 

Programación Dinámica usando Memoización

Teniendo en cuenta la implementación anterior, el siguiente es un árbol de recurrencia parcial para las strings de entrada «AXYT» y «AYZX»  

                       lcs("AXYT", "AYZX")
                       /                 \
         lcs("AXY", "AYZX")            lcs("AXYT", "AYZ")
         /           \                   /               \
lcs("AX", "AYZX") lcs("AXY", "AYZ")   lcs("AXY", "AYZ") lcs("AXYT", "AY")

En el árbol de recursión parcial anterior, lcs(“AXY”, “AYZ”) se resuelven dos veces . Al dibujar el árbol de recursión completo, se ha observado que hay muchos subproblemas que se resuelven una y otra vez. Por lo tanto, este problema tiene la propiedad de subestructura superpuesta y el recálculo de los mismos subproblemas se puede evitar utilizando Memoization o Tabulation . El método de tabulación se ha discutido aquí.  
Un punto común de observación para usar la memorización en el código recursivo serán los dos argumentos no constantes M y Nen cada llamada de función. La función tiene 4 argumentos, pero 2 argumentos son constantes, lo que no afecta la memorización. Las llamadas repetitivas ocurren para N y M que han sido llamados previamente. Seguir los pasos a continuación nos ayudará a escribir la solución DP utilizando la memorización. 

  • Use una array 2-D para almacenar el valor calculado de lcs(m, n) en arr[m-1][n-1] ya que el índice de string comienza desde 0.
  • Siempre que se vuelva a llamar a la función con el mismo argumento m y n, no realice ninguna llamada recursiva adicional y devuelva arr[m-1][n-1] ya que el cálculo anterior de lcs(m, n) ya se ha almacenado en arr[m-1][n-1] , lo que reduce las llamadas recursivas que ocurren más de una vez.

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

C++

// C++ program to memoize
// recursive implementation of LCS problem
#include <bits/stdc++.h>
using namespace std;
 
const int maximum = 1000;
 
// Returns length of LCS for X[0..m-1], Y[0..n-1] */
// memoization applied in recursive solution
int lcs(string X, string Y, int m, int n, int dp[][maximum])
{
    // base case
    if (m == 0 || n == 0)
        return 0;
 
    // if the same state has already been
    // computed
    if (dp[m - 1][n - 1] != -1)
        return dp[m - 1][n - 1];
 
    // if equal, then we store the value of the
    // function call
    if (X[m - 1] == Y[n - 1]) {
 
        // store it in arr to avoid further repetitive
        // work in future function calls
        dp[m - 1][n - 1] = 1 + lcs(X, Y, m - 1, n - 1, dp);
 
        return dp[m - 1][n - 1];
    }
    else {
 
        // store it in arr to avoid further repetitive
        // work in future function calls
        dp[m - 1][n - 1] = max(lcs(X, Y, m, n - 1, dp),
                               lcs(X, Y, m - 1, n, dp));
 
        return dp[m - 1][n - 1];
    }
}
 
// Driver Code
int main()
{
 
    string X = "AGGTAB";
    string Y = "GXTXAYB";
    int m = X.length();
    int n = Y.length();
 
    int dp[m][maximum];
 
    // assign -1 to all positions
    memset(dp, -1, sizeof(dp));
 
    cout << "Length of LCS: " << lcs(X, Y, m, n, dp);
 
    return 0;
}

Java

import java.util.Arrays;
 
// Java program to memoize
// recursive implementation of LCS problem
class GFG {
 
    static final int maximum = 1000;
 
// Returns length of LCS for X[0..m-1], Y[0..n-1] */
// memoization applied in recursive solution
    static int lcs(String X, String Y, int m, int n, int dp[][]) {
        // base case
        if (m == 0 || n == 0) {
            return 0;
        }
 
        // if the same state has already been
        // computed
        if (dp[m - 1][n - 1] != -1) {
            return dp[m - 1][n - 1];
        }
 
        // if equal, then we store the value of the
        // function call
        if (X.charAt(m - 1) == Y.charAt(n - 1)) {
 
            // store it in arr to avoid further repetitive
            // work in future function calls
            dp[m - 1][n - 1] = 1 + lcs(X, Y, m - 1, n - 1, dp);
 
            return dp[m - 1][n - 1];
        } else {
 
            // store it in arr to avoid further repetitive
            // work in future function calls
            dp[m - 1][n - 1] = Math.max(lcs(X, Y, m, n - 1, dp),
                    lcs(X, Y, m - 1, n, dp));
 
            return dp[m - 1][n - 1];
        }
    }
 
// Driver Code
    public static void main(String[] args) {
        String X = "AGGTAB";
        String Y = "GXTXAYB";
        int m = X.length();
        int n = Y.length();
 
        int dp[][] = new int[m][maximum];
 
        // assign -1 to all positions
        for (int[] row : dp) {
            Arrays.fill(row, -1);
        }
 
        System.out.println("Length of LCS: " + lcs(X, Y, m, n, dp));
    }
}
/* This Java code is contributed by 29AjayKumar*/

Python3

# Python3 program to memoize
# recursive implementation of LCS problem
maximum = 1000
 
# Returns length of LCS for X[0..m-1], Y[0..n-1] */
# memoization applied in recursive solution
def lcs(X, Y, m, n, dp):
     
    # base case
    if (m == 0 or n == 0):
        return 0
 
    # if the same state has already been
    # computed
    if (dp[m - 1][n - 1] != -1):
        return dp[m - 1][n - 1]
 
    # if equal, then we store the value of the
    # function call
    if (X[m - 1] == Y[n - 1]):
 
        # store it in arr to avoid further repetitive
        # work in future function calls
        dp[m - 1][n - 1] = 1 + lcs(X, Y, m - 1, n - 1, dp)
 
        return dp[m - 1][n - 1]
 
    else :
 
        # store it in arr to avoid further repetitive
        # work in future function calls
        dp[m - 1][n - 1] = max(lcs(X, Y, m, n - 1, dp),
                               lcs(X, Y, m - 1, n, dp))
 
        return dp[m - 1][n - 1]
 
# Driver Code
X = "AGGTAB"
Y = "GXTXAYB"
m = len(X)
n = len(Y)
 
dp = [[-1 for i in range(maximum)]
          for i in range(m)]
 
print("Length of LCS:", lcs(X, Y, m, n, dp))
 
# This code is contributed by Mohit Kumar

C#

// C# program to memoize
// recursive implementation of LCS problem
using System;
 
class GFG
{
static readonly int maximum = 1000;
 
// Returns length of LCS for
// X[0..m-1], Y[0..n-1]
// memoization applied in
// recursive solution
static int lcs(String X, String Y,
               int m, int n, int [,]dp)
{
    // base case
    if (m == 0 || n == 0)
    {
        return 0;
    }
 
    // if the same state has already been
    // computed
    if (dp[m - 1, n - 1] != -1)
    {
        return dp[m - 1, n - 1];
    }
 
    // if equal, then we store the value
    // of the function call
    if (X[m - 1] == Y[n - 1])
    {
 
        // store it in arr to avoid
        // further repetitive work
        // in future function calls
        dp[m - 1,
           n - 1] = 1 + lcs(X, Y, m - 1,
                                  n - 1, dp);
 
        return dp[m - 1, n - 1];
    }
    else
    {
 
        // store it in arr to avoid
        // further repetitive work
        // in future function calls
        dp[m - 1,
           n - 1] = Math.Max(lcs(X, Y, m, n - 1, dp),
                             lcs(X, Y, m - 1, n, dp));
 
        return dp[m - 1, n - 1];
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    String X = "AGGTAB";
    String Y = "GXTXAYB";
    int m = X.Length;
    int n = Y.Length;
 
    int [,]dp = new int[m, maximum];
 
    // assign -1 to all positions
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < maximum; j++)
        {
            dp[i, j] = -1;
        }
    }
    Console.WriteLine("Length of LCS: " +
                    lcs(X, Y, m, n, dp));
}
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
// Javascript program to memoize
// recursive implementation of LCS problem
 
let maximum = 1000;
 
// Returns length of LCS for X[0..m-1], Y[0..n-1] */
// memoization applied in recursive solution
function lcs(X,Y,m,n,dp)
{
    // base case
        if (m == 0 || n == 0) {
            return 0;
        }
  
        // if the same state has already been
        // computed
        if (dp[m - 1][n - 1] != -1) {
            return dp[m - 1][n - 1];
        }
  
        // if equal, then we store the value of the
        // function call
        if (X[m-1] == Y[n-1]) {
  
            // store it in arr to avoid further repetitive
            // work in future function calls
            dp[m - 1][n - 1] = 1 + lcs(X, Y, m - 1, n - 1, dp);
  
            return dp[m - 1][n - 1];
        } else {
  
            // store it in arr to avoid further repetitive
            // work in future function calls
            dp[m - 1][n - 1] = Math.max(lcs(X, Y, m, n - 1, dp),
                    lcs(X, Y, m - 1, n, dp));
  
            return dp[m - 1][n - 1];
        }
}
 
// Driver Code
let X = "AGGTAB";
let Y = "GXTXAYB";
let m = X.length;
let n = Y.length;
 
let dp=new Array(m);
for(let i=0;i<dp.length;i++)
{
    dp[i]=new Array(maximum);
    for(let j=0;j<dp[i].length;j++)
    {
        dp[i][j]=-1;
    }
}
 
document.write("Length of LCS: " + lcs(X, Y, m, n, dp));
 
     
 
// This code is contributed by avanitrachhadiya2155
</script>
Producción: 

Length of LCS: 4

 

Complejidad de tiempo: O(N * M), donde N y M son longitudes de la primera y segunda string respectivamente. 
Espacio Auxiliar: (N*M)
 

Publicación traducida automáticamente

Artículo escrito por Striver y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *