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.
Sean las secuencias de entrada 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]) = MÁX ( L(X[0..m-2], Y[0..n-1]), L(X[0..m-1], Y[0..n-2])
/* A Naive recursive implementation of LCS problem in java*/
public class LongestCommonSubsequence {
/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs(char[] X, char[] 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));
}
/* Utility function to get max of 2 integers */
int max(int a, int b)
{
return (a > b) ? a : b;
}
public static void main(String[] args)
{
LongestCommonSubsequence lcs = new LongestCommonSubsequence();
String s1 = "AGGTAB";
String s2 = "GXTXAYB";
char[] X = s1.toCharArray();
char[] Y = s2.toCharArray();
int m = X.length;
int n = Y.length;
System.out.println("Length of LCS is"
+ " " + lcs.lcs(X, Y, m, n));
}
}
// This Code is Contributed by Saket Kumar
Length of LCS is 4
A continuación se muestra una implementación tabulada para el problema LCS.
/* Dynamic Programming Java implementation of LCS problem */
public class LongestCommonSubsequence {
/* 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[][] = 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]);
}
}
return L[m][n];
}
/* Utility function to get max of 2 integers */
int max(int a, int b)
{
return (a > b) ? a : b;
}
public static void main(String[] args)
{
LongestCommonSubsequence lcs = new LongestCommonSubsequence();
String s1 = "AGGTAB";
String s2 = "GXTXAYB";
char[] X = s1.toCharArray();
char[] Y = s2.toCharArray();
int m = X.length;
int n = Y.length;
System.out.println("Length of LCS is"
+ " " + lcs.lcs(X, Y, m, n));
}
}
// This Code is Contributed by Saket Kumar
Length of LCS is 4
Consulte el artículo completo sobre programación dinámica | ¡ Establezca 4 (Subsecuencia común más larga) para obtener más detalles!
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