El Longest Common Su­b­se­que­n­ce (LCS) es un problema clásico en in­fo­r­má­ti­ca. Las so­lu­cio­nes para resolver el problema LCS aparecen a menudo en en­tre­vi­s­tas de pro­gra­ma­ción y cursos de al­go­ri­t­mos.

¿En qué consiste el problema de la Longest Common Su­b­se­que­n­ce?

El objetivo es encontrar la su­b­se­cue­n­cia común más larga (“Longest Common Su­b­se­que­n­ce”) de dos se­cue­n­cias. Una su­b­se­cue­n­cia se deriva de una secuencia original. La su­b­se­cue­n­cia tiene el mismo orden de elementos, pero algunos pueden haber sido eli­mi­na­dos. 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 di­fe­re­n­cia im­po­r­ta­n­te entre la su­b­se­cue­n­cia común más larga y la subcadena común más larga (“longest common substring”). Una subcadena, a di­fe­re­n­cia de la su­b­se­cue­n­cia, no puede contener espacios. Uti­li­za­n­do el ejemplo DAVID / DANIEL, la su­b­se­cue­n­cia común más larga sería “DA”, ya que “I” está in­te­rru­m­pi­da por “V” y “N” re­s­pe­c­ti­va­me­n­te.

Un ejemplo práctico del problema de la LCS

El problema de la Longest Common Su­b­se­que­n­ce es im­po­r­ta­n­te en todos los ámbitos en los que se trabaje con se­cue­n­cias derivadas unas de otras. Las so­lu­cio­nes para encontrar la LCS se utilizan, por ejemplo, para examinar textos en busca de si­mi­li­tu­des y di­fe­re­n­cias. De esta forma puede de­te­c­tar­se 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 bioi­n­fo­r­má­ti­ca, el problema de la Longest Common Su­b­se­que­n­ce se utiliza en el análisis de se­cue­n­cias de ADN. Las mu­ta­cio­nes alteran las bases del ADN en po­si­cio­nes in­di­vi­dua­les a lo largo del tiempo. La presencia de una secuencia común más larga entre dos se­cue­n­cias indica un alto pa­re­n­te­s­co genético. De este modo, se pueden rastrear los avances genéticos entre especies a lo largo de la evolución.

Los li­n­güi­s­tas utilizan el problema de la Longest Common Su­b­se­que­n­ce para estudiar la evolución de las lenguas a lo largo de los siglos. Si se en­cue­n­tran dos palabras de lenguas di­fe­re­n­tes que tienen el mismo si­g­ni­fi­ca­do 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 co­rre­s­po­n­de­n­cia de las letras.

¿Cómo funcionan las so­lu­cio­nes al problema de la Longest Common Su­b­se­que­n­ce?

El problema LCS puede re­so­l­ve­r­se, en primer lugar, con un pla­n­tea­mie­n­to “ingenuo” sin ninguna op­ti­mi­za­ción o abordaje especial. Se de­te­r­mi­nan todas las su­b­se­cue­n­cias de las dos se­cue­n­cias 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 se­cue­n­cias cortas.

A co­n­ti­nua­ción, te mostramos tres enfoques más efi­cie­n­tes del problema LCS:

  1. Enfoque recursivo
  2. Op­ti­mi­za­ción mediante me­moi­za­ción
  3. Pro­gra­ma­ción dinámica

Todos los enfoques tienen en común la di­s­ti­n­ción de tres casos con respecto a dos se­cue­n­cias:

  • La última letra es igual
  • La última letra no es igual
  • La longitud de una de las se­cue­n­cias es cero

Los enfoques difieren en co­m­ple­ji­dad temporal (tiempo de ejecución asi­n­tó­ti­co) y espacial (re­qui­si­tos de memoria):

Enfoque Tiempo de ejecución Memoria requerida
Enfoque ingenuo O(n * n²) O(n)
Enfoque recursivo O(n²) O(1)
Op­ti­mi­za­ción por me­moi­za­ción O(n *m) O(n* m)
Pro­gra­ma­ción dinámica O(n *m) O(n* m)
Nota

Cada uno de los al­go­ri­t­mos que se presentan a co­n­ti­nua­ción determina la longitud de la su­b­se­cue­n­cia común más larga. Puede haber varias su­b­se­cue­n­cias concretas de esta longitud que pueden de­te­r­mi­nar­se mediante otros pasos.

De­te­r­mi­nar re­cu­r­si­va­me­n­te la Longest Common Su­b­se­que­n­ce

Al examinar el problema LCS, resulta evidente que tiene una “su­b­e­s­tru­c­tu­ra óptima”. Esto significa que el problema puede reducirse a su­b­pro­ble­mas. Para encontrar la solución, un enfoque recursivo es idóneo. Te mostramos la im­ple­me­n­ta­ción del algoritmo en tres lenguajes de pro­gra­ma­ció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))
# Let's test
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
  • Gratis SSL Wildcard para tra­n­s­fe­re­n­cias de datos más seguras
  • Gratis registro privado para más pri­va­ci­dad

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++

Op­ti­mi­za­ción del enfoque recursivo mediante me­moi­za­ción

Un examen más detallado del pla­n­tea­mie­n­to recursivo calcula su­b­se­cue­n­cias solapadas. Esta propiedad, de­no­mi­na­da “su­pe­r­po­si­ción de su­b­pro­ble­mas”, es conocida como la secuencia de Fibonacci. También en este caso, las partes re­cu­r­si­vas 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 me­moi­za­ción. En otras palabras, al­ma­ce­na­mos en caché los su­b­pro­ble­mas ya ca­l­cu­la­dos en una matriz bi­di­me­n­sio­nal.

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++

Pro­gra­ma­ción dinámica de la Longest Common Su­b­se­que­n­ce

La pro­gra­ma­ción dinámica es una técnica no recursiva para resolver problemas de op­ti­mi­za­ción di­vi­dié­n­do­los en su­b­pro­ble­mas más pequeños y re­so­l­vié­n­do­los de abajo arriba. La pro­gra­ma­ción dinámica se aplica, entre otras cosas, como método de solución para al­go­ri­t­mos de pa­th­fi­n­di­ng. El problema de la Longest Common Su­b­se­que­n­ce también puede re­so­l­ve­r­se mediante pro­gra­ma­ción dinámica uti­li­za­n­do una matriz bi­di­me­n­sio­nal.

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++
Ir al menú principal