Encuentre la subcadena común más larga en C++

1. Subcadena común más larga
2. Formulación del problema de la subcadena común más larga

En este artículo, discutiremos el problema de subcadena común más largo y su solución usando programación dinámica en C++.

Subcadena común más larga

La subcadena común más larga (LCS) es un problema bien conocido en informática. Una subcadena de longitud máxima en dos o más cadenas es la subcadena común más larga.

Por ejemplo, considere las siguientes tres cadenas:

1. XYXYZ
2. YXYZX
3. XYZYX

La subcadena común más larga de estas tres cadenas es XYZ. Existen otras subcadenas comunes en estas tres cadenas como X, XY, Y, YX, YZ y Z; sin embargo, la subcadena común más larga es solo XYZ.

La figura 1 muestra la subcadena común más larga de las tres cadenas anteriores:

Formulación del problema de la subcadena común más larga

Considere dos cadenas, S1 y S2, con longitudes m y n, respectivamente, para encontrar la subcadena exacta de S1 y S2, con la longitud máxima.

Presentaremos dos soluciones a este problema:

1. Una solución sencilla
2. Solución de programación dinámica

Una solución sencilla

Los siguientes son los pasos para encontrar la subcadena común más larga de dos cadenas usando la solución simple:

Esta solución puede encontrar la subcadena común más larga; sin embargo, llevará tiempo, así que veamos la solución de programación dinámica para lograr el mismo objetivo en menos tiempo.

Encuentre la subcadena común más larga a través de la programación dinámica

Podemos usar programación dinámica (DP) para encontrar la subcadena común más larga (LCS) de dos cadenas. El siguiente es el pseudocódigo para encontrar la subcadena común más larga utilizando el enfoque de programación dinámica:

function Longest_Common_Substring(S1[1..m], S2[1..n])
    DP_Matrix = array(1..m, 1..n)
    len = 0
    result_substring = {}
    for i = 1..m
        for j = 1..n
            if S1[i] == S2[j]
                if i = 1 or j = 1
                    DP_Matrix[i, j] = 1
                else
                    DP_Matrix[i, j] = DP_Matrix[i − 1, j − 1] + 1
                if DP_Matrix[i, j] > len
                    len = DP_Matrix[i, j]
                    result_substring = {S1[i − len + 1..i]}
                else if DP_Matrix[i, j] == len
                    result_substring = result_substring ∪ {S1[i − len + 1..i]}
            else
                DP_Matrix[i, j] = 0
    return result_substring

La solución anterior requiere una complejidad de tiempo cuadrática (es decir, $\mathcal{O}(mn)$) para calcular la subcadena común más larga. La solución es óptima y siempre garantiza la subcoincidencia más larga.

Nota: Las matrices en pseudocódigos comienzan desde el índice 1. Además, este algoritmo funciona bien solo con cadenas no vacías.

La DP_Matrix es una matriz o matriz 2D que se utiliza como una tabla de programación dinámica para almacenar la longitud de la subcadena para los prefijos S1[1..i] y S2[1..j] con las posiciones finales S1[i] y S2[j].

La variable len se utiliza para almacenar la longitud actual más grande de result_substring, que se ha encontrado hasta ahora. La subcadena se utiliza para almacenar la cadena de longitud len.

Todas las celdas de la primera fila y columna de la matriz_DP se inicializan en 1. Se utiliza una función objetivo para calcular las celdas restantes.

La función objetivo para esta formulación se puede presentar como:

1. Para una celda dada DP_Matrix[i,j], si los caracteres correspondientes de las secuencias de cadenas dadas (es decir, los caracteres en S1[i] y S2[j] coinciden, entonces agregamos 1 al valor de la celda DP_Matrix[i-1,j-1].
   • Si el valor actualizado de la celda DP_Matrix[i,j] es mayor que la longitud anterior de la subcadena, actualice len con este nuevo valor.
   • Simultáneamente, guarde esta nueva cadena máxima en un soporte de cadena auxiliar (es decir, result_substring).
2. Si los caracteres correspondientes no coinciden (es decir, un caso de discrepancia), configure la celda DP_Matrix[i, j] con un valor cero, lo que indica que solo una nueva subcadena puede comenzar desde aquí.

Después de todas las iteraciones M*N (es decir, el final de los bucles for), result_substring tendrá una subcadena común óptimamente más grande.

Solución de programación dinámica de subcadena común más larga en C++

El siguiente código se usa para encontrar la subcadena común más larga de las cadenas usando programación dinámica en C++.

#include <iostream>
#include <string>
using namespace std;

string Longest_Common_Substring(string Str1, string Str2) {
  string result_substring = "";
  int m = Str1.length();
  int n = Str2.length();
  int DP_Matrix[m + 1][n + 1];
  int len = 0;
  int end = 0;

  for (int i = 0; i <= m; i++) {
    for (int j = 0; j <= n; j++) {
      if (Str1[i] == Str2[j]) {
        if ((i == 0) || (j == 0))
          DP_Matrix[i][j] = 1;
        else
          DP_Matrix[i][j] = 1 + DP_Matrix[i - 1][j - 1];

        if (DP_Matrix[i][j] > len) {
          len = DP_Matrix[i][j];
          int start = i - DP_Matrix[i][j] + 1;
          if (end == start) {
            result_substring.push_back(Str1[i]);
          } else {
            end = start;
            result_substring.clear();
            result_substring.append(Str1.substr(end, (i + 1) - end));
          }
        }
      } else {
        DP_Matrix[i][j] = 0;
      }
    }
  }
  return result_substring;
}

int main() {
  string String1, String2;
  cout << "Enter the first string: ";
  cin >> String1;
  cout << "Enter the second string: ";
  cin >> String2;
  string substring = Longest_Common_Substring(String1, String2);
  cout << "LCS of " << String1 << " and " << String2 << " is " << substring
       << " of Length " << substring.length() << endl;
  return 0;
}

El código anterior contiene la función Longest_Common_Substring, que acepta dos cadenas (es decir, String1 y String2) como parámetro y devuelve su subcadena común óptima más grande. La función Longest_Common_Substring utiliza el método de tabla de programación dinámica para encontrar este LCS.

En el código anterior, DP_Matrix es una matriz de enteros 2D que almacena la mejor longitud de subcadena actual para el subpar de cadenas S1[1..i] y S2[1..j]. El result_substring, como se explica en la explicación del pseudocódigo, se utiliza para almacenar la subcadena más larga encontrada.

Veamos los resultados del código anterior para diferentes pares de cadenas:

Salida 1:

Enter the first string: ATGCACATA
Enter the second string: GCAATGCACT
LCS of ATGCACATA and GCAATGCACT is ATGCAC of Length 6

Salida 2:

Enter the first string: ABCDDFA
Enter the second string: DCDDACDDF
LCS of ABCDDFA and DCDDACDDF is CDDF of Length 4

Además de la prueba teórica o matemática, los resultados anteriores sugieren que la solución de programación dinámica discutida es óptima.