El problema de la Longest Common Subsequence

El Longest Common Subsequence (LCS) es un problema clásico en informática. Las soluciones para resolver el problema LCS aparecen a menudo en entrevistas de programación y cursos de algoritmos.

¿En qué consiste el problema de la Longest Common Subsequence?

El objetivo es encontrar la subsecuencia común más larga (“Longest Common Subsequence”) de dos secuencias. Una subsecuencia se deriva de una secuencia original. La subsecuencia tiene el mismo orden de elementos, pero algunos pueden haber sido eliminados. Te mostramos este principio con algunos ejemplos:

Secuencia X Secuencia Y LCS(X, Y)
FATHER VATER ATER
MOTHER MUTTER MTER
DAVID DANIEL DAI
Nota

Existe una diferencia importante entre la subsecuencia común más larga y la subcadena común más larga (“longest common substring”). Una subcadena, a diferencia de la subsecuencia, no puede contener espacios. Utilizando el ejemplo DAVID / DANIEL, la subsecuencia común más larga sería “DA”, ya que “I” está interrumpida por “V” y “N” respectivamente.

Un ejemplo práctico del problema de la LCS

El problema de la Longest Common Subsequence es importante en todos los ámbitos en los que se trabaje con secuencias derivadas unas de otras. Las soluciones para encontrar la LCS se utilizan, por ejemplo, para examinar textos en busca de similitudes y diferencias. De esta forma puede detectarse el plagio. La conocida utilidad “diff”, que muestra los cambios en archivos de código fuente, también se basa en el problema LCS.

En bioinformática, el problema de la Longest Common Subsequence se utiliza en el análisis de secuencias de ADN. Las mutaciones alteran las bases del ADN en posiciones individuales a lo largo del tiempo. La presencia de una secuencia común más larga entre dos secuencias indica un alto parentesco genético. De este modo, se pueden rastrear los avances genéticos entre especies a lo largo de la evolución.

Los lingüistas utilizan el problema de la Longest Common Subsequence para estudiar la evolución de las lenguas a lo largo de los siglos. Si se encuentran dos palabras de lenguas diferentes que tienen el mismo significado y comparten una secuencia común larga, esto indica un origen común. De esta forma, la evolución histórica puede deducirse a partir de la correspondencia de las letras.

¿Cómo funcionan las soluciones al problema de la Longest Common Subsequence?

El problema LCS puede resolverse, en primer lugar, con un planteamiento “ingenuo” sin ninguna optimización o abordaje especial. Se determinan todas las subsecuencias de las dos secuencias y se encuentra la secuencia más larga que ambas tienen en común. Este enfoque no es del todo eficiente y solo es adecuado para secuencias cortas.

A continuación, te mostramos tres enfoques más eficientes del problema LCS:

  1. Enfoque recursivo
  2. Optimización mediante memoización
  3. Programación dinámica

Todos los enfoques tienen en común la distinción de tres casos con respecto a dos secuencias:

  • La última letra es igual
  • La última letra no es igual
  • La longitud de una de las secuencias es cero

Los enfoques difieren en complejidad temporal (tiempo de ejecución asintótico) y espacial (requisitos de memoria):

Enfoque Tiempo de ejecución Memoria requerida
Enfoque ingenuo O(n * n²) O(n)
Enfoque recursivo O(n²) O(1)
Optimización por memoización O(n *m) O(n* m)
Programación dinámica O(n *m) O(n* m)
Nota

Cada uno de los algoritmos que se presentan a continuación determina la longitud de la subsecuencia común más larga. Puede haber varias subsecuencias concretas de esta longitud que pueden determinarse mediante otros pasos.

Determinar recursivamente la Longest Common Subsequence

Al examinar el problema LCS, resulta evidente que tiene una “subestructura óptima”. Esto significa que el problema puede reducirse a subproblemas. Para encontrar la solución, un enfoque recursivo es idóneo. Te mostramos la implementación del algoritmo en tres lenguajes de programación populares.

Python

def lcs(X, Y, m, n):
    # Base case
    if m == 0 or n == 0:
        return 0
    # Last elements are equal
    elif X[m-1] == Y[n-1]:
        return 1 + lcs(X, Y, m-1, n-1)
    # Last elements differ
    else:
        return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n))
X, Y = "DANIEL", "DAVID"
lcs_len = lcs(X, Y, len(X), len(Y))
print(f"Length of LCS is: {lcs_len}")
python

Java

import java.io.*;
class LCS {
    public static int lcs(String A, String B, int m, int n)
    {
        // Base case
        if (m == 0 || n == 0)
            return 0;
        // Last elements are equal
        if (A.charAt(m - 1) == B.charAt(n - 1))
            return 1 + lcs(A, B, m - 1, n - 1);
        // Last elements differ
        else
            return Math.max(lcs(A, B, m, n - 1),
             lcs(A, B, m - 1, n));
    }
    
    // Let's test
    public static void main(String[] args)
        {
            String X = "DAVID";
            String Y = "DANIEL";
            int lcsLength = LCS.lcs(X, Y, X.length(), Y.length());
            System.out.println("Length of LCS is: " + lcsLength);
        }
}
java
Dominios web
Compra y registra tu dominio ideal
  • Domina el mercado con nuestra oferta 3x1 en dominios
  • Tu dominio protegido con SSL Wildcard gratis
  • 1 cuenta de correo electrónico por contrato

C++

#include <iostream>
using namespace std;
int lcs(string X, string Y, int m, int n)
{
    // Base case
    if (m == 0 || n == 0) {
        return 0;
    }
    // Last elements are equal
    if (X[m - 1] == Y[n - 1]) {
        return 1 + lcs(X, Y, m - 1, n - 1);
    }
    // Last elements differ
    else {
        return max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n));
    }
}
// Let's test
int main()
{
    // Initialize variables
    string X = "DAVID";
    string Y = "DANIEL";
    // Compute and output length of LCS
    cout << "Length of LCS is " << lcs(X, Y, X.size(), Y.size());
    return 0;
}
c++

Optimización del enfoque recursivo mediante memoización

Un examen más detallado del planteamiento recursivo calcula subsecuencias solapadas. Esta propiedad, denominada “superposición de subproblemas”, es conocida como la secuencia de Fibonacci. También en este caso, las partes recursivas se calculan una y otra vez para llegar a la solución. Para que el proceso sea más eficiente, es muy práctico utilizar la memoización. En otras palabras, almacenamos en caché los subproblemas ya calculados en una matriz bidimensional.

Python

def lcs(X, Y, m, n, table):
    
    # Base case
    if (m == 0 or n == 0):
        return 0
    # Already computed value at given position
    if (table[m][n] != -1):
        return table[m][n]
    # Last elements are equal
    if X[m - 1] == Y[n - 1]:
        table[m][n] = 1 + lcs(X, Y, m - 1, n - 1, table)
    # Last elements differ
    else:
        table[m][n] = max(lcs(X, Y, m, n - 1, table), lcs(X, Y, m - 1, n, table))
    return table[m][n]
# Let's test
X = "DAVID"
Y = "DANIEL"
m, n = len(X), len(Y)
# Initialize table fields to `-1`
table = [[-1 for i in range(n + 1)] for j in range(m + 1)]
// Compute and output length of LCS
print(f"Length of LCS is: {lcs(X, Y, m, n, table)}")
python

Java

import java.io.*;
class LCS {
    public static int lcs(String X, String Y, int m, int n, int[][] table) {
        // Base case
        if (m == 0 || n == 0) {
            return 0;
        }
        // Already computed value at given position
        if (table[m][n] != -1) {
            return table[m][n];
        }
        // Last elements are equal
        if(X.charAt(m - 1) == Y.charAt(n - 1)) {
            table[m][n] = 1 + lcs(X, Y, m - 1, n - 1, table);
            return table[m][n];
        }
        // Last elements differ
        else {
            table[m][n] = Math.max(lcs(X, Y, m, n - 1, table),lcs(X, Y, m - 1, n, table));
            return table[m][n];
        }
    }
    // Let's test
    public static void main(String args[]){
        // Initialize variables
        String X = "DAVID";
        String Y = "DANIEL";
        int m = X.length();
        int n = Y.length();
        int[][] table = new int[m + 1][n + 1];
        
        // Initialize table fields to `-1`
        for(int i=0; i < m + 1; i++) {
            for(int j=0; j < n + 1; j++) {
                table[i][j] = -1;
            }
        }
        // Compute and output length of LCS
        int lcsLength = lcs(X, Y, m, n, table);
        System.out.println("Length of LCS is: " + lcsLength);
    }
}
java

C++

#include <bits/stdc++.h>
using namespace std;
int lcs(char *X, char* Y, int m, int n, vector<vector<int>>& table)
{
    // Base case
    if (m == 0 || n == 0)
        return 0;
    // Already computed value at given position
    if (table[m][n] != -1) {
        return table[m][n];
    }
    // Last elements are equal
    if (X[m - 1] == Y[n - 1]) {
        table[m][n] = 1 + lcs(X, Y, m - 1, n - 1, table);
        return table[m][n];
    }
    // Last elements differ
    else { 
        table[m][n] = max(lcs(X, Y, m, n - 1, table), lcs(X, Y, m - 1, n, table));
        return table;
    }
}
// Let's test
int main()
{
    // Initialize variables
    char X[] = "DAVID";
    char Y[] = "DANIEL";
    int m = strlen(X);
    int n = strlen(Y);
    // Initialize table with `-1`
    vector<vector<int>> table(m + 1, vector<int>(n + 1, -1));
    
    // Compute and output length of LCS
    cout << "Length of LCS is: " << lcs(X, Y, m, n, table);
    return 0;
}
c++

Programación dinámica de la Longest Common Subsequence

La programación dinámica es una técnica no recursiva para resolver problemas de optimización dividiéndolos en subproblemas más pequeños y resolviéndolos de abajo arriba. La programación dinámica se aplica, entre otras cosas, como método de solución para algoritmos de pathfinding. El problema de la Longest Common Subsequence también puede resolverse mediante programación dinámica utilizando una matriz bidimensional.

Python

def lcs(X , Y, m, n): 
    
    # Initialize dynamic programming table fields to `None`
    table = [[None] * (n + 1) for _ in range(m + 1)]
    
    # Compute table values
    for i in range(m + 1):
        for j in range(n + 1):
            # Base case
            if i == 0 or j == 0 :
                table[i][j] = 0
            # Last elements are equal
            elif X[i - 1] == Y[j - 1]:
                table[i][j] = table[i - 1][j - 1]+ 1
            # Last elements differ
            else:
                table[i][j] = max(table[i - 1][j] , table[i][j - 1])
    
    return table[m][n]
# Let's test
X = "DAVID"
Y = "DANIEL"
# Compute and output length of LCS
lcs_len = lcs(X, Y, len(X), len(Y))
print(f"Length of LCS is: {lcs_len}")
python

Java

import java.io.*;
class LCS {
    public static int lcs(String X, String Y, int m, int n)
    {
        // Initialize dynamic programming table fields
        int table[][] = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                // Base case
                if (i == 0 || j == 0)
                    table[i][j] = 0;
                // Last elements are equal
                else if (X.charAt(i - 1) == Y.charAt(j - 1))
                    table[i][j] = table[i - 1][j - 1] + 1;
                // Last elements differ
                else
                    table[i][j] = Math.max(table[i - 1][j], table[i][j - 1]);
            }
        }
        return table[m][n];
    }
    // Let's test
    public static void main(String args[]){
        // Initialize variables
        String X = "DAVID";
        String Y = "DANIEL";
        int m = X.length();
        int n = Y.length();
        // Compute and output length of LCS
        int lcsLength = lcs(X, Y, m, n);
        System.out.println("Length of LCS is: " + lcsLength);
    }
}
java

C++

#include <bits/stdc++.h>
using namespace std;
int lcs(string X, string Y, int m, int n) {
	// Initialize dynamic programming table
	int table[m + 1][n + 1];
	// Compute table values
	for (int i = 0; i <= m; i++) {
		for (int j = 0; j <= n; j++) {
			// Base case
			if (i == 0 || j == 0)
				table[i][j] = 0;
			// Last elements are equal
			else if (X[i - 1] == Y[j - 1])
				table[i][j] = table[i - 1][j - 1] + 1;
			// Last elements differ
			else
				table[i][j] = max(table[i - 1][j], table[i][j - 1]);
		}
	}
	return table[m][n];
}
// Let's test
int main() {
  // Initialize variables
  string X = "DAVID";
  string Y = "DANIEL";
  int m = X.size();
  int n = Y.size();
  // Compute and output length of LCS
  cout << "Length of LCS is " << lcs(X, Y, m, n);
  return 0;
}
c++
¿Le ha resultado útil este artículo?