Dadas dos strings str1 y str2, la tarea es encontrar la longitud de la string más corta que tiene tanto str1 como str2 como subsecuencias.
Ejemplos:
Input: str1 = "geek", str2 = "eke" Output: 5 Explanation: String "geeke" has both string "geek" and "eke" as subsequences. Input: str1 = "AGGTAB", str2 = "GXTXAYB" Output: 9 Explanation: String "AGXGTXAYB" has both string "AGGTAB" and "GXTXAYB" as subsequences.
Este problema está estrechamente relacionado con el problema de la subsecuencia común más larga . A continuación se muestran los pasos.
1) Encuentra la subsecuencia común más larga (lcs) de dos strings dadas. Por ejemplo, lcs de «geek» y «eke» es «ek».
2) Inserte caracteres que no sean lcs (en su orden original en strings) en los lcs que se encuentran arriba y devuelva el resultado. Así que «ek» se convierte en «geeke», que es la supersecuencia común más corta.
Consideremos otro ejemplo, str1 = «AGGTAB» y str2 = «GXTXAYB». LCS de str1 y str2 es «GTAB». Una vez que encontramos LCS, insertamos caracteres de ambas strings en orden y obtenemos «AGXGTXAYB»
¿Cómo funciona esto?
Necesitamos encontrar una string que tenga ambas strings como subsecuencias y que sea la string más corta. Si ambas strings tienen todos los caracteres diferentes, el resultado es la suma de las longitudes de dos strings dadas. Si hay caracteres comunes, no los queremos varias veces, ya que la tarea es minimizar la longitud. Por lo tanto, primero encontramos la subsecuencia común más larga, tomamos una aparición de esta subsecuencia y agregamos caracteres adicionales.
Length of the shortest supersequence = (Sum of lengths of given two strings) - (Length of LCS of two given strings)
A continuación se muestra la implementación de la idea anterior. La siguiente implementación solo encuentra la longitud de la supersecuencia más corta.
C++
// C++ program to find length of the
// shortest supersequence
#include <bits/stdc++.h>
using namespace std;
// Utility function to get max
// of 2 integers
int max(int a, int b) { return (a > b) ? a : b; }
// Returns length of LCS for
// X[0..m - 1], Y[0..n - 1]
int lcs(char* X, char* Y, int m, int n);
// Function to find length of the
// shortest supersequence of X and Y.
int shortestSuperSequence(char* X, char* Y)
{
int m = strlen(X), n = strlen(Y);
// find lcs
int l = lcs(X, Y, m, n);
// Result is sum of input string
// lengths - length of lcs
return (m + n - l);
}
// Returns length of LCS
// for X[0..m - 1], Y[0..n - 1]
int lcs(char* X, char* Y, int m, int n)
{
int L[m + 1][n + 1];
int 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];
}
// Driver code
int main()
{
char X[] = "AGGTAB";
char Y[] = "GXTXAYB";
cout << "Length of the shortest supersequence is "
<< shortestSuperSequence(X, Y) << endl;
return 0;
}
// This code is contributed by Akanksha Rai
C
// C program to find length of
// the shortest supersequence
#include <stdio.h>
#include <string.h>
// Utility function to get
// max of 2 integers
int max(int a, int b) { return (a > b) ? a : b; }
// Returns length of LCS for
// X[0..m - 1], Y[0..n - 1]
int lcs(char* X, char* Y, int m, int n);
// Function to find length of the
// shortest supersequence of X and Y.
int shortestSuperSequence(char* X, char* Y)
{
int m = strlen(X), n = strlen(Y);
// find lcs
int l = lcs(X, Y, m, n);
// Result is sum of input string
// lengths - length of lcs
return (m + n - l);
}
// Returns length of LCS
// for X[0..m - 1], Y[0..n - 1]
int lcs(char* X, char* Y, int m, int n)
{
int L[m + 1][n + 1];
int 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];
}
// Driver code
int main()
{
char X[] = "AGGTAB";
char Y[] = "GXTXAYB";
printf("Length of the shortest supersequence is %d\n",
shortestSuperSequence(X, Y));
return 0;
}
Java
// Java program to find length of
// the shortest supersequence
class GFG {
// Function to find length of the
// shortest supersequence of X and Y.
static int shortestSuperSequence(String X, String Y)
{
int m = X.length();
int n = Y.length();
// find lcs
int l = lcs(X, Y, m, n);
// Result is sum of input string
// lengths - length of lcs
return (m + n - l);
}
// Returns length of LCS
// for X[0..m - 1], Y[0..n - 1]
static int lcs(String X, String Y, int m, int n)
{
int[][] L = new int[m + 1][n + 1];
int 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.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]);
}
}
// L[m][n] contains length of LCS
// for X[0..n - 1] and Y[0..m - 1]
return L[m][n];
}
// Driver code
public static void main(String args[])
{
String X = "AGGTAB";
String Y = "GXTXAYB";
System.out.println("Length of the shortest "
+ "supersequence is "
+ shortestSuperSequence(X, Y));
}
}
// This article is contributed by Sumit Ghosh
Python3
# Python program to find length
# of the shortest supersequence
# Function to find length of the
# shortest supersequence of X and Y.
def shortestSuperSequence(X, Y):
m = len(X)
n = len(Y)
l = lcs(X, Y, m, n)
# Result is sum of input string
# lengths - length of lcs
return (m + n - l)
# Returns length of LCS for
# X[0..m - 1], Y[0..n - 1]
def lcs(X, Y, m, n):
L = [[0] * (n + 2) for i in
range(m + 2)]
# 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])
# L[m][n] contains length of
# LCS for X[0..n - 1] and Y[0..m - 1]
return L[m][n]
# Driver code
X = "AGGTAB"
Y = "GXTXAYB"
print("Length of the shortest supersequence is %d"
% shortestSuperSequence(X, Y))
# This code is contributed by Ansu Kumari
C#
// C# program to find length of
// the shortest supersequence
using System;
class GFG {
// Function to find length of the
// shortest supersequence of X and Y.
static int shortestSuperSequence(String X, String Y)
{
int m = X.Length;
int n = Y.Length;
// find lcs
int l = lcs(X, Y, m, n);
// Result is sum of input string
// lengths - length of lcs
return (m + n - l);
}
// Returns length of LCS for
// X[0..m - 1], Y[0..n - 1]
static int lcs(String X, String Y, int m, int n)
{
int[, ] L = new int[m + 1, n + 1];
int 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] = 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];
}
// Driver code
public static void Main()
{
String X = "AGGTAB";
String Y = "GXTXAYB";
Console.WriteLine("Length of the shortest"
+ "supersequence is "
+ shortestSuperSequence(X, Y));
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program to find length of the
// shortest supersequence
// Function to find length of the
// shortest supersequence of X and Y.
function shortestSuperSequence($X, $Y)
{
$m = strlen($X);
$n = strlen($Y);
// find lcs
$l = lcs($X, $Y, $m, $n);
// Result is sum of input string
// lengths - length of lcs
return ($m + $n - $l);
}
// 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, 0));
// 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];
}
// Driver code
$X = "AGGTAB";
$Y = "GXTXAYB";
echo "Length of the shortest supersequence is ".
shortestSuperSequence($X, $Y)."\n";
// This code is contributed by mits
?>
Javascript
<script>
// javascript program to find length of
// the shortest supersequence // Function to find length of the
// shortest supersequence of X and Y.
function shortestSuperSequence(X, Y)
{
var m = X.length;
var n = Y.length;
// find lcs
var l = lcs(X, Y, m, n);
// Result is sum of input string
// lengths - length of lcs
return (m + n - l);
}
// Returns length of LCS
// for X[0..m - 1], Y[0..n - 1]
function lcs(X, Y , m , n)
{
var L = Array(m+1).fill(0).map(x => Array(n+1).fill(0));
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.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]);
}
}
// L[m][n] contains length of LCS
// for X[0..n - 1] and Y[0..m - 1]
return L[m][n];
}
// Driver code
var X = "AGGTAB";
var Y = "GXTXAYB";
document.write("Length of the shortest "
+ "supersequence is "
+ shortestSuperSequence(X, Y));
// This code contributed by shikhasingrajput
</script>
Producción:
Length of the shortest supersequence is 9
Complejidad temporal: O(m*n).
A continuación se muestra otro método para resolver el problema anterior.
Un análisis simple produce una solución recursiva por debajo de la simple.
Let X[0..m - 1] and Y[0..n - 1] be two
strings and m and n be respective
lengths.
if (m == 0) return n;
if (n == 0) return m;
// If last characters are same, then
// add 1 to result and
// recur for X[]
if (X[m - 1] == Y[n - 1])
return 1 + SCS(X, Y, m - 1, n - 1);
// Else find shortest of following two
// a) Remove last character from X and recur
// b) Remove last character from Y and recur
else
return 1 + min( SCS(X, Y, m - 1, n), SCS(X, Y, m, n - 1) );
A continuación se muestra una solución recursiva ingenua simple basada en la fórmula recursiva anterior.
C++
// A Naive recursive C++ program to find
// length of the shortest supersequence
#include <bits/stdc++.h>
using namespace std;
int superSeq(char* X, char* Y, int m, int n)
{
if (!m)
return n;
if (!n)
return m;
if (X[m - 1] == Y[n - 1])
return 1 + superSeq(X, Y, m - 1, n - 1);
return 1
+ min(superSeq(X, Y, m - 1, n),
superSeq(X, Y, m, n - 1));
}
// Driver Code
int main()
{
char X[] = "AGGTAB";
char Y[] = "GXTXAYB";
cout << "Length of the shortest supersequence is "
<< superSeq(X, Y, strlen(X), strlen(Y));
return 0;
}
Java
// A Naive recursive Java program to find
// length of the shortest supersequence
class GFG {
static int superSeq(String X, String Y, int m, int n)
{
if (m == 0)
return n;
if (n == 0)
return m;
if (X.charAt(m - 1) == Y.charAt(n - 1))
return 1 + superSeq(X, Y, m - 1, n - 1);
return 1
+ Math.min(superSeq(X, Y, m - 1, n),
superSeq(X, Y, m, n - 1));
}
// Driver code
public static void main(String args[])
{
String X = "AGGTAB";
String Y = "GXTXAYB";
System.out.println(
"Length of the shortest"
+ "supersequence is: "
+ superSeq(X, Y, X.length(), Y.length()));
}
}
// This article is contributed by Sumit Ghosh
Python3
# A Naive recursive python program to find
# length of the shortest supersequence
def superSeq(X, Y, m, n):
if (not m):
return n
if (not n):
return m
if (X[m - 1] == Y[n - 1]):
return 1 + superSeq(X, Y, m - 1, n - 1)
return 1 + min(superSeq(X, Y, m - 1, n),
superSeq(X, Y, m, n - 1))
# Driver Code
X = "AGGTAB"
Y = "GXTXAYB"
print("Length of the shortest supersequence is %d"
% superSeq(X, Y, len(X), len(Y)))
# This code is contributed by Ansu Kumari
C#
// A Naive recursive C# program to find
// length of the shortest supersequence
using System;
class GFG {
static int superSeq(String X, String Y, int m, int n)
{
if (m == 0)
return n;
if (n == 0)
return m;
if (X[m - 1] == Y[n - 1])
return 1 + superSeq(X, Y, m - 1, n - 1);
return 1
+ Math.Min(superSeq(X, Y, m - 1, n),
superSeq(X, Y, m, n - 1));
}
// Driver Code
public static void Main()
{
String X = "AGGTAB";
String Y = "GXTXAYB";
Console.WriteLine(
"Length of the shortest supersequence is: "
+ superSeq(X, Y, X.Length, Y.Length));
}
}
// This code is contributed by Sam007
PHP
<?php
// A Naive recursive PHP program to find
// length of the shortest supersequence
function superSeq($X, $Y, $m, $n)
{
if (!$m)
return $n;
if (!$n)
return $m;
if ($X[$m - 1] == $Y[$n - 1])
return 1 + superSeq($X, $Y, $m - 1, $n - 1);
return 1 + min(superSeq($X, $Y, $m - 1, $n),
superSeq($X, $Y, $m, $n - 1));
}
// Driver Code
$X = "AGGTAB";
$Y = "GXTXAYB";
echo "Length of the shortest supersequence is ",
superSeq($X, $Y, strlen($X), strlen($Y));
// This code is contributed by Ryuga
?>
Javascript
<script>
// A Naive recursive javascript program to find
// length of the shortest supersequence
function superSeq(X, Y , m , n)
{
if (m == 0)
return n;
if (n == 0)
return m;
if (X.charAt(m - 1) == Y.charAt(n - 1))
return 1 + superSeq(X, Y, m - 1, n - 1);
return 1
+ Math.min(superSeq(X, Y, m - 1, n),
superSeq(X, Y, m, n - 1));
}
// Driver code
var X = "AGGTAB";
var Y = "GXTXAYB";
document.write(
"Length of the shortest"
+ "supersequence is "
+ superSeq(X, Y, X.length, Y.length));
// This code contributed by Princi Singh
</script>
Producción:
Length of the shortest supersequence is 9
Complejidad del tiempo: O(2 min(m, n) ) . Dado que hay subproblemas superpuestos , podemos resolver este problema recursivo de manera eficiente utilizando la Programación Dinámica. A continuación se muestra la implementación basada en la programación dinámica.
C++
// A dynamic programming based C program to
// find length of the shortest supersequence
#include <bits/stdc++.h>
using namespace std;
// Returns length of the shortest
// supersequence of X and Y
int superSeq(char* X, char* Y, int m, int n)
{
int dp[m + 1][n + 1];
// Fill table in bottom up manner
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
// Below steps follow above recurrence
if (!i)
dp[i][j] = j;
else if (!j)
dp[i][j] = i;
else if (X[i - 1] == Y[j - 1])
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j]
= 1 + min(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[m][n];
}
// Driver Code
int main()
{
char X[] = "AGGTAB";
char Y[] = "GXTXAYB";
cout << "Length of the shortest supersequence is "
<< superSeq(X, Y, strlen(X), strlen(Y));
return 0;
}
Java
// A dynamic programming based Java program to
// find length of the shortest supersequence
class GFG {
// Returns length of the shortest
// supersequence of X and Y
static int superSeq(String X, String Y, int m, int n)
{
int[][] dp = new int[m + 1][n + 1];
// Fill table in bottom up manner
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
// Below steps follow above recurrence
if (i == 0)
dp[i][j] = j;
else if (j == 0)
dp[i][j] = i;
else if (X.charAt(i - 1) == Y.charAt(j - 1))
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = 1
+ Math.min(dp[i - 1][j],
dp[i][j - 1]);
}
}
return dp[m][n];
}
// Driver Code
public static void main(String args[])
{
String X = "AGGTAB";
String Y = "GXTXAYB";
System.out.println(
"Length of the shortest supersequence is "
+ superSeq(X, Y, X.length(), Y.length()));
}
}
// This article is contributed by Sumit Ghosh
Python3
# A dynamic programming based python program
# to find length of the shortest supersequence
# Returns length of the shortest supersequence of X and Y
def superSeq(X, Y, m, n):
dp = [[0] * (n + 2) for i in range(m + 2)]
# Fill table in bottom up manner
for i in range(m + 1):
for j in range(n + 1):
# Below steps follow above recurrence
if (not i):
dp[i][j] = j
elif (not j):
dp[i][j] = i
elif (X[i - 1] == Y[j - 1]):
dp[i][j] = 1 + dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j],
dp[i][j - 1])
return dp[m][n]
# Driver Code
X = "AGGTAB"
Y = "GXTXAYB"
print("Length of the shortest supersequence is %d"
% superSeq(X, Y, len(X), len(Y)))
# This code is contributed by Ansu Kumari
C#
// A dynamic programming based C# program to
// find length of the shortest supersequence
using System;
class GFG {
// Returns length of the shortest
// supersequence of X and Y
static int superSeq(String X, String Y, int m, int n)
{
int[, ] dp = new int[m + 1, n + 1];
// Fill table in bottom up manner
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
// Below steps follow above recurrence
if (i == 0)
dp[i, j] = j;
else if (j == 0)
dp[i, j] = i;
else if (X[i - 1] == Y[j - 1])
dp[i, j] = 1 + dp[i - 1, j - 1];
else
dp[i, j] = 1
+ Math.Min(dp[i - 1, j],
dp[i, j - 1]);
}
}
return dp[m, n];
}
// Driver code
public static void Main()
{
String X = "AGGTAB";
String Y = "GXTXAYB";
Console.WriteLine(
"Length of the shortest supersequence is "
+ superSeq(X, Y, X.Length, Y.Length));
}
}
// This code is contributed by Sam007
PHP
<?php
// A dynamic programming based PHP program to
// find length of the shortest supersequence
// Returns length of the shortest
// supersequence of X and Y
function superSeq($X, $Y, $m, $n)
{
$dp = array_fill(0, $m + 1,
array_fill(0, $n + 1, 0));
// Fill table in bottom up manner
for ($i = 0; $i <= $m; $i++)
{
for ($j = 0; $j <= $n; $j++)
{
// Below steps follow above recurrence
if (!$i)
$dp[$i][$j] = $j;
else if (!$j)
$dp[$i][$j] = $i;
else if ($X[$i - 1] == $Y[$j - 1])
$dp[$i][$j] = 1 + $dp[$i - 1][$j - 1];
else
$dp[$i][$j] = 1 + min($dp[$i - 1][$j],
$dp[$i][$j - 1]);
}
}
return $dp[$m][$n];
}
// Driver Code
$X = "AGGTAB";
$Y = "GXTXAYB";
echo "Length of the shortest supersequence is " .
superSeq($X, $Y, strlen($X), strlen($Y));
// This code is contributed by mits
?>
Javascript
<script>
// A dynamic programming based javascript program to
// find length of the shortest supersequence
// Returns length of the shortest
// supersequence of X and Y
function superSeq(X, Y, m, n)
{
var dp = Array(m+1).fill(0).map(x => Array(n+1).fill(0));
// Fill table in bottom up manner
for (var i = 0; i <= m; i++)
{
for (var j = 0; j <= n; j++)
{
// Below steps follow above recurrence
if (i == 0)
dp[i][j] = j;
else if (j == 0)
dp[i][j] = i;
else if (X.charAt(i - 1) == Y.charAt(j - 1))
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = 1
+ Math.min(dp[i - 1][j],
dp[i][j - 1]);
}
}
return dp[m][n];
}
// Driver Code
var X = "AGGTAB";
var Y = "GXTXAYB";
document.write(
"Length of the shortest supersequence is "
+ superSeq(X, Y, X.length, Y.length));
// This code is contributed by 29AjayKumar
</script>
Producción:
Length of the shortest supersequence is 9
Complejidad temporal: O(m*n).
Gracias a Gaurav Ahirwar por sugerir esta solución.
Enfoque de memorización de arriba hacia abajo:
la idea es seguir la solución recursiva simple, usar una tabla de búsqueda para evitar volver a calcular. Antes de calcular el resultado de una entrada, verificamos si el resultado ya se calculó o no. Si ya se calculó, devolvemos ese resultado.
C++
// A dynamic programming based python program
// to find length of the shortest supersequence
// Returns length of the
// shortest supersequence of X and Y
#include <bits/stdc++.h>
using namespace std;
int superSeq(string X, string Y, int n, int m,
vector<vector<int> > lookup)
{
if (m == 0 || n == 0) {
lookup[n][m] = n + m;
}
if (lookup[n][m] == 0)
if (X[n - 1] == Y[m - 1]) {
lookup[n][m]
= superSeq(X, Y, n - 1, m - 1, lookup) + 1;
}
else {
lookup[n][m]
= min(superSeq(X, Y, n - 1, m, lookup) + 1,
superSeq(X, Y, n, m - 1, lookup) + 1);
}
return lookup[n][m];
}
// Driver Code
int main()
{
string X = "AGGTB";
string Y = "GXTXAYB";
vector<vector<int> > lookup(
X.size() + 1, vector<int>(Y.size() + 1, 0));
cout << "Length of the shortest supersequence is "
<< superSeq(X, Y, X.size(), Y.size(), lookup)
<< endl;
return 0;
}
// This code is contributed by niraj gusain
Java
// A dynamic programming based python program
// to find length of the shortest supersequence
// Returns length of the
// shortest supersequence of X and Y
import java.util.*;
class GFG {
static int superSeq(String X, String Y, int n, int m,
int[][] lookup)
{
if (m == 0 || n == 0) {
lookup[n][m] = n + m;
}
if (lookup[n][m] == 0)
if (X.charAt(n - 1) == Y.charAt(m - 1)) {
lookup[n][m]
= superSeq(X, Y, n - 1, m - 1, lookup)
+ 1;
}
else {
lookup[n][m] = Math.min(
superSeq(X, Y, n - 1, m, lookup) + 1,
superSeq(X, Y, n, m - 1, lookup) + 1);
}
return lookup[n][m];
}
// Driver Code
public static void main(String[] args)
{
String X = "AGGTB";
String Y = "GXTXAYB";
int[][] lookup
= new int[X.length() + 1][Y.length() + 1];
System.out.print(
"Length of the shortest supersequence is "
+ superSeq(X, Y, X.length(), Y.length(), lookup)
+ "\n");
}
}
// This code contributed by umadevi9616
Python3
# A dynamic programming based python program
# to find length of the shortest supersequence
# Returns length of the
# shortest supersequence of X and Y
def superSeq(X,Y,n,m,lookup):
if m==0 or n==0:
lookup[n][m] = n+m
if (lookup[n][m] == 0):
if X[n-1]==Y[m-1]:
lookup[n][m] = superSeq(X,Y,n-1,m-1,lookup)+1
else:
lookup[n][m] = min(superSeq(X,Y,n-1,m,lookup)+1,
superSeq(X,Y,n,m-1,lookup)+1)
return lookup[n][m]
# Driver Code
X = "AGGTAB"
Y = "GXTXAYB"
lookup = [[0 for j in range(len(Y)+1)]for i in range(len(X)+1)]
print("Length of the shortest supersequence is {}"
.format(superSeq(X,Y,len(X),len(Y),lookup)))
# This code is contributed by Tanmay Ambadkar
C#
// A dynamic programming based python program
// to find length of the shortest supersequence
// Returns length of the
// shortest supersequence of X and Y
using System;
public class GFG {
static int superSeq(String X, String Y, int n,
int m, int[,] lookup)
{
if (m == 0 || n == 0) {
lookup[n, m] = n + m;
}
if (lookup[n, m] == 0)
if (X[n - 1] == Y[m - 1]) {
lookup[n, m] = superSeq(X, Y, n - 1,
m - 1, lookup) + 1;
}
else {
lookup[n, m] = Math.Min(superSeq(X, Y, n - 1, m, lookup) +
1, superSeq(X, Y, n, m - 1, lookup) +
1);
}
return lookup[n, m];
}
// Driver Code
public static void Main(String[] args) {
String X = "AGGTB";
String Y = "GXTXAYB";
int[,] lookup = new int[X.Length + 1,Y.Length + 1];
Console.Write(
"Length of the shortest supersequence is " +
superSeq(X, Y, X.Length, Y.Length, lookup) + "\n");
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// A dynamic programming based python program
// to find length of the shortest supersequence
// Returns length of the
// shortest supersequence of X and Y
function superSeq( X, Y , n , m, lookup) {
if (m == 0 || n == 0) {
lookup[n][m] = n + m;
}
if (lookup[n][m] == 0)
if (X.charAt(n - 1) == Y.charAt(m - 1)) {
lookup[n][m] = superSeq(X, Y, n - 1, m - 1, lookup) + 1;
}
else {
lookup[n][m] = Math.min(superSeq(X, Y, n - 1, m, lookup) + 1, superSeq(X, Y, n, m - 1, lookup) + 1);
}
return lookup[n][m];
}
// Driver Code
var X = "AGGTB";
var Y = "GXTXAYB";
var lookup = Array(X.length + 1).fill().map(()=>Array(Y.length + 1).fill(0));
document.write(
"Length of the shortest supersequence is "
+ superSeq(X, Y, X.length, Y.length, lookup) + "\n");
// This code is contributed by gauravrajput1
</script>
Producción:
Length of the shortest supersequence is 9.0
Complejidad temporal: O(n 2 )
Espacio Auxiliar: O(n 2 )
Ejercicio:
Amplíe el programa anterior para imprimir la supersecuencia más corta usando también la función para imprimir LCS .
Consulte Impresión de supersecuencia común más corta para ver la solución
Referencias:
https://en.wikipedia.org/wiki/Shortest_common_supersequence
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente
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