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 */
#include <bits/stdc++.h>
int max(int a, int b);
/* 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;
}
/* Driver program to test above function */
int main()
{
char X[] = "AGGTAB";
char Y[] = "GXTXAYB";
int m = strlen(X);
int n = strlen(Y);
printf("Length of LCS is %d\n", lcs(X, Y, m, n));
return 0;
}
Length of LCS is 4
A continuación se muestra una implementación tabulada para el problema LCS.
/* Dynamic Programming C/C++ implementation of LCS problem */
#include <bits/stdc++.h>
int max(int a, int b);
/* 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];
}
/* Utility function to get max of 2 integers */
int max(int a, int b)
{
return (a > b) ? a : b;
}
/* Driver program to test above function */
int main()
{
char X[] = "AGGTAB";
char Y[] = "GXTXAYB";
int m = strlen(X);
int n = strlen(Y);
printf("Length of LCS is %d\n", lcs(X, Y, m, n));
return 0;
}
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