¿Qué es la subsecuencia común más larga?
Como el nombre sugiere, la subsecuencia común más larga (LCS, por sus siglas en inglés) es la subsecuencia de mayor longitud entre dos cadenas.
Necesitamos definir qué es una subsecuencia.
Subsecuencia
Digamos que tenemos una cadena “ABC”.
Si borramos cero, uno o más caracteres de esta cadena, obtenemos una subsecuencia de esta cadena.
Así que las subsecuencias de la cadena ABC serán: { "A" , "B" , "C" , "AB" , "AC" , "BC" , "ABC" , "" }
La cadena vacía también es una subsecuencia.
Para averiguar la subsecuencia, para cada carácter de una cadena, tenemos dos opciones: tomamos el carácter o no.
Para nuestra cadena “ABC”, tenemos 23 = 8 subsecuencias
Entonces, si la longitud de la cadena es n, existen 2n subsecuencias de esa cadena.
Para nuestra cadena "ABC", la subsecuencia más larga es "ABC"
Ejemplo: Las subsecuencias comunes entre "HELLOM" y "HMLD" son "H" , "HL" , "HM", etc.
Aquí "HLL" es la subsecuencia común más larga entre las cadenas "HELLOM" y HMLD.
Métodos de resolución
Bottom Up
Para el modelo Bottom-Up, llenaremos nuestro arreglo bidimensional de forma iterativa.
Siguiendo este modelo, tendremos que calcular todas las posibles subsecuencias.
Siguiendo esta forma, la complejidad del algoritmo siempre será O(mn).
Top Down
El modelo Top-Down surge como una optimización de la forma recursiva tradicional (fuerza bruta).
Lo que haremos será almacenar los cálculos que vayamos haciendo, para evitar tener que calcularnos nuevamente con cada ejecución del algoritmo recursivo. Esta técnica se conoce como memoización.
Al evitar la repetición de cálculos, la complejidad de nuestro algoritmo decrece radicalmente. Pasando de una complejidad O(2n) a una complejidad O(mn).
Implementaciones en C++
Bottom Up - Iterativa
Complejidad ~ O(mn)
#include <iostream>
using namespace std;
void lcs(string &X, string &Y, int m, int n)
{
int L[m + 1][n + 1];
// Llenado de tabla en forma bottom-up
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]);
}
}
// Código para obtener el LCS
int index = L[m][n];
// Inicializar cadena y agregar símbolo de fin de cadena.
// Se hace de esta forma para evitar tener que invertir
// la cadena al final.
char lcs[index + 1];
lcs[index] = '\0';
// Empezar desde la esquina inferior derecha
int i = m, j = n;
while (i > 0 && j > 0)
{
// Si los caracteres son iguales,
// agregar al principio.
if (X[i - 1] == Y[j - 1])
{
lcs[index - 1] = X[i - 1];
i--;
j--;
index--;
}
// Caso contrario, encontrar el mayor
// y moverse en esa dirección
else if (L[i - 1][j] > L[i][j - 1])
i--;
else
j--;
}
cout << lcs << endl;
}
int main()
{
string X = "AGGTAB";
string Y = "GXTXAYB";
int m = X.length();
int n = Y.length();
lcs(X, Y, m, n);
return 0;
}
// Imprime GTAB
Top Down - Memoización
Complejidad ~ O(mn)
#include <iostream>
using namespace std;
const int max = 1000;
// Llenado de tabla en forma top-down
int lcs(string X, string Y, int m, int n, int memo[][max])
{
// Caso base recursión
if (m == 0 || n == 0)
return 0;
// Revisar si el paso actual ha sido calculado
// previamente
if (memo[m - 1][n - 1] != -1)
{
return memo[m - 1][n - 1];
}
// Si son iguales, almacenamos el valor de
// la llamada a función
else if (X[m - 1] == Y[n - 1])
{
memo[m - 1][n - 1] = 1 + lcs(X, Y, m - 1, n - 1, memo);
return memo[m - 1][n - 1];
}
else
{
memo[m - 1][n - 1] = max(lcs(X, Y, m, n - 1, memo),
lcs(X, Y, m - 1, n, memo));
return memo[m - 1][n - 1];
}
}
int main()
{
string X = "AGGTAB";
string Y = "GXTXAYB";
int m = X.length();
int n = Y.length();
int memo[m][max];
// Llenar la tabla de -1s
memset(memo, -1, sizeof(memo));
cout << "La longitud del LCS es: " << lcs(X, Y, m, n, memo) << endl;
return 0;
}