Dadas dos strings, encuentre la longitud de la subsecuencia más larga presente en ambas.
Ejemplos:
LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3. LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4.
Hemos discutido una solución típica basada en programación dinámica para LCS . Podemos optimizar el espacio utilizado por el problema LCS. Sabemos que la relación de recurrencia del problema LCS es
CPP
/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs(string &X, string &Y)
{
int m = X.length(), n = Y.length();
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]);
}
}
/* L[m][n] contains length of LCS for X[0..n-1] and
Y[0..m-1] */
return L[m][n];
}
Java
class GFG {
// Returns length of LCS for X[0..m-1], Y[0..n-1]
public static int lcs(String X, String Y)
{
// Find lengths of two strings
int m = X.length(), n = Y.length();
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] = max(L[i - 1][j], L[i][j - 1]);
}
}
/* L[m][n] contains length of LCS for X[0..n-1] and
Y[0..m-1] */
return L[m][n];
}
}
// This code is contributed by rajsanghavi9.
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Returns length of LCS for X[0..m-1], Y[0..n-1]
public static int lcs(string X, string Y)
{
// Find lengths of two strings
int m = X.Length, n = Y.Length;
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]);
}
}
/* L[m][n] contains length of LCS for X[0..n-1] and
Y[0..m-1] */
return L[m, n];
}
}
// this code is contributed by code_hunt.
Javascript
<script>
// Dynamic Programming Java implementation of LCS problem
// Utility function to get max of 2 integers
function max(a, b)
{
if (a > b)
return a;
else
return b;
}
// Returns length of LCS for X[0..m-1], Y[0..n-1]
function lcs(X, Y, m, n)
{
var L = new Array(m + 1);
for(var i = 0; i < L.length; i++)
{
L[i] = new Array(n + 1);
}
var i, j;
/* 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]);
}
}
/* L[m][n] contains length of LCS
for X[0..n-1] and Y[0..m-1] */
return L[m][n];
}
// This code is contributed by akshitsaxenaa09.
</script>
¿Cómo encontrar la longitud de LCS es O (n) espacio auxiliar?
Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.
Una observación importante en la implementación simple anterior es que, en cada iteración del ciclo externo, solo necesitamos valores de todas las columnas de la fila anterior . Por lo tanto, no es necesario almacenar todas las filas en nuestra array DP, solo podemos almacenar dos filas a la vez y usarlas. De esa forma, el espacio utilizado se reducirá de L[m+1][n+1] a L[2][n+1]. A continuación se muestra la implementación de la idea anterior.
C++
// Space optimized C++ implementation
// of LCS problem
#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)
{
// Find lengths of two strings
int m = X.length(), n = Y.length();
int L[2][n + 1];
// Binary index, used to
// index current row and
// previous row.
bool bi;
for (int i = 0; i <= m; i++)
{
// Compute current
// binary index
bi = i & 1;
for (int j = 0; j <= n; j++)
{
if (i == 0 || j == 0)
L[bi][j] = 0;
else if (X[i-1] == Y[j-1])
L[bi][j] = L[1 - bi][j - 1] + 1;
else
L[bi][j] = max(L[1 - bi][j],
L[bi][j - 1]);
}
}
// Last filled entry contains
// length of LCS
// for X[0..n-1] and Y[0..m-1]
return L[bi][n];
}
// Driver code
int main()
{
string X = "AGGTAB";
string Y = "GXTXAYB";
printf("Length of LCS is %d\n", lcs(X, Y));
return 0;
}
Java
// Java Code for A Space Optimized
// Solution of LCS
class GFG {
// Returns length of LCS
// for X[0..m - 1],
// Y[0..n - 1]
public static int lcs(String X,
String Y)
{
// Find lengths of two strings
int m = X.length(), n = Y.length();
int L[][] = new int[2][n+1];
// Binary index, used to index
// current row and previous row.
int bi=0;
for (int i = 0; i <= m; i++)
{
// Compute current binary index
bi = i & 1;
for (int j = 0; j <= n; j++)
{
if (i == 0 || j == 0)
L[bi][j] = 0;
else if (X.charAt(i - 1) ==
Y.charAt(j - 1))
L[bi][j] = L[1 - bi][j - 1] + 1;
else
L[bi][j] = Math.max(L[1 - bi][j],
L[bi][j - 1]);
}
}
// Last filled entry contains length of
// LCS for X[0..n-1] and Y[0..m-1]
return L[bi][n];
}
// Driver Code
public static void main(String[] args)
{
String X = "AGGTAB";
String Y = "GXTXAYB";
System.out.println("Length of LCS is " +
lcs(X, Y));
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# Space optimized Python
# implementation of LCS problem
# Returns length of LCS for
# X[0..m-1], Y[0..n-1]
def lcs(X, Y):
# Find lengths of two strings
m = len(X)
n = len(Y)
L = [[0 for i in range(n+1)] for j in range(2)]
# Binary index, used to index current row and
# previous row.
bi = bool
for i in range(m):
# Compute current binary index
bi = i&1
for j in range(n+1):
if (i == 0 or j == 0):
L[bi][j] = 0
elif (X[i] == Y[j - 1]):
L[bi][j] = L[1 - bi][j - 1] + 1
else:
L[bi][j] = max(L[1 - bi][j],
L[bi][j - 1])
# Last filled entry contains length of LCS
# for X[0..n-1] and Y[0..m-1]
return L[bi][n]
# Driver Code
X = "AGGTAB"
Y = "GXTXAYB"
print("Length of LCS is", lcs(X, Y))
# This code is contributed by Soumen Ghosh.
C#
// C# Code for A Space
// Optimized Solution of LCS
using System;
class GFG
{
// Returns length of LCS
// for X[0..m - 1],
// Y[0..n - 1]
public static int lcs(string X,
string Y)
{
// Find lengths of
// two strings
int m = X.Length, n = Y.Length;
int [,]L = new int[2, n + 1];
// Binary index, used to
// index current row and
// previous row.
int bi = 0;
for (int i = 0; i <= m; i++)
{
// Compute current
// binary index
bi = i & 1;
for (int j = 0; j <= n; j++)
{
if (i == 0 || j == 0)
L[bi, j] = 0;
else if (X[i - 1] == Y[j - 1])
L[bi, j] = L[1 - bi,
j - 1] + 1;
else
L[bi, j] = Math.Max(L[1 - bi, j],
L[bi, j - 1]);
}
}
// Last filled entry contains
// length of LCS for X[0..n-1]
// and Y[0..m-1]
return L[bi, n];
}
// Driver Code
public static void Main()
{
string X = "AGGTAB";
string Y = "GXTXAYB";
Console.Write("Length of LCS is " +
lcs(X, Y));
}
}
// This code is contributed
// by shiv_bhakt.
PHP
<?php
// Space optimized PHP implementation
// of LCS problem
// Returns length of LCS
// for X[0..m-1], Y[0..n-1]
function lcs($X, $Y)
{
// Find lengths of two strings
$m = strlen($X);
$n = strlen($Y);
$L = array(array());
// Binary index, used to index
// current row and previous row.
for ($i = 0; $i <= $m; $i++)
{
// Compute current binary index
$bi = $i & 1;
for ($j = 0; $j <= $n; $j++)
{
if ($i == 0 || $j == 0)
$L[$bi][$j] = 0;
else if ($X[$i - 1] == $Y[$j - 1])
$L[$bi][$j] = $L[1 - $bi][$j - 1] + 1;
else
$L[$bi][$j] = max($L[1 - $bi][$j],
$L[$bi][$j - 1]);
}
}
// Last filled entry contains
// length of LCS
// for X[0..n-1] and Y[0..m-1]
return $L[$bi][$n];
}
// Driver code
$X = "AGGTAB";
$Y = "GXTXAYB";
echo "Length of LCS is : ",
lcs($X, $Y);
// This code is contributed by Ryuga
?>
Javascript
<script>
// Javascript Code for A Space Optimized Solution of LCS
// Returns length of LCS
// for X[0..m - 1],
// Y[0..n - 1]
function lcs(X, Y)
{
// Find lengths of two strings
let m = X.length, n = Y.length;
let L = new Array(2);
for (let i = 0; i < 2; i++)
{
L[i] = new Array(n + 1);
for (let j = 0; j < n + 1; j++)
{
L[i][j] = 0;
}
}
// Binary index, used to index
// current row and previous row.
let bi=0;
for (let i = 0; i <= m; i++)
{
// Compute current binary index
bi = i & 1;
for (let j = 0; j <= n; j++)
{
if (i == 0 || j == 0)
L[bi][j] = 0;
else if (X[i - 1] ==
Y[j - 1])
L[bi][j] = L[1 - bi][j - 1] + 1;
else
L[bi][j] = Math.max(L[1 - bi][j],
L[bi][j - 1]);
}
}
// Last filled entry contains length of
// LCS for X[0..n-1] and Y[0..m-1]
return L[bi][n];
}
let X = "AGGTAB";
let Y = "GXTXAYB";
document.write("Length of LCS is " +
lcs(X, Y));
</script>
Producción
Length of LCS is 4
Tiempo Complejidad : O(m*n)
Espacio Auxiliar : O(n)
Este artículo es una contribución de Shivam Mittal . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Podemos mejorar aún más la complejidad del espacio del programa anterior
Python3
def lcs(text1, text2):
m, n = len(text1), len(text2)
if m > n : text1, text2 = text2, text1
dp = [0] * (n + 1)
for c in text1:
prev = 0
for i, d in enumerate(text2):
prev, dp[i + 1] = dp[i + 1], prev + 1 if c == d else max(dp[i], dp[i + 1])
return dp[-1]
X = "AGGTAB"
Y = "GXTXAYB"
print("Length of LCS is", lcs(X, Y))
# This code is contributed by Tushar Khera .
Java
/*package whatever //do not write package name here */
class GFG {
public static int lcs(String text1, String text2) {
int[] dp = new int[text2.length()+1];
for(int i = 0; i< text1.length(); i++){
int prev = dp[0];
for(int j = 1; j < dp.length; j++){
int temp = dp[j];
if(text1.charAt(i) != text2.charAt(j-1)){
dp[j] = Math.max(dp[j-1], dp[j]);
}else{
dp[j] = prev +1;
}
prev = temp;
}
}
return dp[dp.length-1];
}
public static void main(String[] args)
{
String X = "AGGTAB";
String Y = "GXTXAYB";
System.out.println("Length of LCS is " + lcs(X, Y));
}
}
# This code is contributed by Tushar Khera .
Producción
Length of LCS is 4
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA