Subsecuencia común más larga

Tabla de contenido

Uso de la programación dinámica para encontrar el LCS
Algoritmo de subsecuencia común más largo
Ejemplos de Python, Java y C / C ++
Aplicaciones posteriores comunes más extensas

En este tutorial, aprenderá cómo se encuentra la subsecuencia común más larga. Además, encontrará ejemplos prácticos de la subsecuencia común más larga en C, C ++, Java y Python.

La subsecuencia común más larga (LCS) se define como la subsecuencia más larga que es común a todas las secuencias dadas, siempre que no se requiera que los elementos de la subsecuencia ocupen posiciones consecutivas dentro de las secuencias originales.

Si S1 y S2 son las dos secuencias dadas, Z es la subsecuencia común de S1 y S2 si Z es una subsecuencia de S1 y S2. Además, Z debe ser una secuencia estrictamente creciente de los índices de S1 y S2.

En una secuencia estrictamente creciente, los índices de los elementos elegidos de las secuencias originales deben estar en orden ascendente en Z.

 S1 = (B, C, D, A, A, C, D)

Entonces, (A, D, B)no puede ser una subsecuencia de S1 ya que el orden de los elementos no es el mismo (es decir, no es una secuencia estrictamente creciente).

Entendamos LCS con un ejemplo.

 S1 = (B, C, D, A, A, C, D) S2 = (A, C, D, B, A, C)

Entonces, las subsecuencias comunes son (B, C), (C, D, A, C), (D, A, C), (A, A, C), (A, C), (C, D), …

Entre estas subsecuencias, se (C, D, A, C)encuentra la subsecuencia común más larga. Vamos a encontrar esta subsecuencia común más larga usando programación dinámica.

Antes de continuar, si aún no conoce la programación dinámica, consulte la programación dinámica.

Uso de la programación dinámica para encontrar el LCS

Tomemos dos secuencias:

La primera secuencia

Segunda secuencia

Se siguen los siguientes pasos para encontrar la subsecuencia común más larga.

Cree una tabla de dimensión n+1*m+1donde nym son las longitudes de X e Y respectivamente. La primera fila y la primera columna están llenas de ceros. Inicializar una tabla
Llene cada celda de la tabla usando la siguiente lógica.
Si el carácter correspondiente a la fila actual y la columna actual coinciden, llene la celda actual agregando uno al elemento diagonal. Apunta una flecha a la celda diagonal.
De lo contrario, tome el valor máximo de la columna anterior y el elemento de la fila anterior para llenar la celda actual. Apunte una flecha a la celda con valor máximo. Si son iguales, señale cualquiera de ellos. Llena los valores
El paso 2 se repite hasta que se llena la tabla. Completa todos los valores
El valor de la última fila y la última columna es la longitud de la subsecuencia común más larga. La esquina inferior derecha es la longitud del LCS
Para encontrar la subsecuencia común más larga, comience desde el último elemento y siga la dirección de la flecha. Los elementos correspondientes al símbolo () forman la subsecuencia común más larga. Crea un camino de acuerdo con las flechas

Por tanto, la subsecuencia común más larga es CD.

LCS

¿Cómo es un algoritmo de programación dinámica más eficiente que el algoritmo recursivo al resolver un problema LCS?

El método de programación dinámica reduce el número de llamadas a funciones. Almacena el resultado de cada llamada de función para que pueda usarse en futuras llamadas sin necesidad de llamadas redundantes.

En el algoritmo dinámico anterior, los resultados obtenidos de cada comparación entre los elementos de X y los elementos de Y se almacenan en una tabla para que se puedan utilizar en cálculos futuros.

Por lo tanto, el tiempo que toma un enfoque dinámico es el tiempo que toma llenar la tabla (es decir, O (mn)). Considerando que, el algoritmo de recursividad tiene la complejidad de 2 ^{max (m, n)} .

Algoritmo de subsecuencia común más largo

 X e Y son dos secuencias dadas Inicializar una tabla LCS de dimensión X.length * Y.length X.label = X Y.label = Y LCS (0) () = 0 LCS () (0) = 0 Start from LCS ( 1) (1) Compare X (i) e Y (j) Si X (i) = Y (j) LCS (i) (j) = 1 + LCS (i-1, j-1) Apunte una flecha a LCS (i) (j) Else LCS (i) (j) = max (LCS (i-1) (j), LCS (i) (j-1)) Apunte una flecha hacia max (LCS (i-1) ( j), LCS (i) (j-1))

Ejemplos de Python, Java y C / C ++

Python Java C C ++

 # The longest common subsequence in Python # Function to find lcs_algo def lcs_algo(S1, S2, m, n): L = ((0 for x in range(n+1)) for x in range(m+1)) # Building the mtrix in bottom-up way for i in range(m+1): for j in range(n+1): if i == 0 or j == 0: L(i)(j) = 0 elif S1(i-1) == S2(j-1): L(i)(j) = L(i-1)(j-1) + 1 else: L(i)(j) = max(L(i-1)(j), L(i)(j-1)) index = L(m)(n) lcs_algo = ("") * (index+1) lcs_algo(index) = "" i = m j = n while i> 0 and j> 0: if S1(i-1) == S2(j-1): lcs_algo(index-1) = S1(i-1) i -= 1 j -= 1 index -= 1 elif L(i-1)(j)> L(i)(j-1): i -= 1 else: j -= 1 # Printing the sub sequences print("S1 : " + S1 + "S2 : " + S2) print("LCS: " + "".join(lcs_algo)) S1 = "ACADB" S2 = "CBDA" m = len(S1) n = len(S2) lcs_algo(S1, S2, m, n)

 // The longest common subsequence in Java class LCS_ALGO ( static void lcs(String S1, String S2, int m, int n) ( int()() LCS_table = new int(m + 1)(n + 1); // Building the mtrix in bottom-up way for (int i = 0; i <= m; i++) ( for (int j = 0; j <= n; j++) ( if (i == 0 || j == 0) LCS_table(i)(j) = 0; else if (S1.charAt(i - 1) == S2.charAt(j - 1)) LCS_table(i)(j) = LCS_table(i - 1)(j - 1) + 1; else LCS_table(i)(j) = Math.max(LCS_table(i - 1)(j), LCS_table(i)(j - 1)); ) ) int index = LCS_table(m)(n); int temp = index; char() lcs = new char(index + 1); lcs(index) = ''; int i = m, j = n; while (i> 0 && j> 0) ( if (S1.charAt(i - 1) == S2.charAt(j - 1)) ( lcs(index - 1) = S1.charAt(i - 1); i--; j--; index--; ) else if (LCS_table(i - 1)(j)> LCS_table(i)(j - 1)) i--; else j--; ) // Printing the sub sequences System.out.print("S1 : " + S1 + "S2 : " + S2 + "LCS: "); for (int k = 0; k <= temp; k++) System.out.print(lcs(k)); System.out.println(""); ) public static void main(String() args) ( String S1 = "ACADB"; String S2 = "CBDA"; int m = S1.length(); int n = S2.length(); lcs(S1, S2, m, n); ) )

 // The longest common subsequence in C #include #include int i, j, m, n, LCS_table(20)(20); char S1(20) = "ACADB", S2(20) = "CBDA", b(20)(20); void lcsAlgo() ( m = strlen(S1); n = strlen(S2); // Filling 0's in the matrix for (i = 0; i <= m; i++) LCS_table(i)(0) = 0; for (i = 0; i <= n; i++) LCS_table(0)(i) = 0; // Building the mtrix in bottom-up way for (i = 1; i <= m; i++) for (j = 1; j = LCS_table(i)(j - 1)) ( LCS_table(i)(j) = LCS_table(i - 1)(j); ) else ( LCS_table(i)(j) = LCS_table(i)(j - 1); ) ) int index = LCS_table(m)(n); char lcsAlgo(index + 1); lcsAlgo(index) = ''; int i = m, j = n; while (i> 0 && j> 0) ( if (S1(i - 1) == S2(j - 1)) ( lcsAlgo(index - 1) = S1(i - 1); i--; j--; index--; ) else if (LCS_table(i - 1)(j)> LCS_table(i)(j - 1)) i--; else j--; ) // Printing the sub sequences printf("S1 : %s S2 : %s ", S1, S2); printf("LCS: %s", lcsAlgo); ) int main() ( lcsAlgo(); printf(""); )

 // The longest common subsequence in C++ #include using namespace std; void lcsAlgo(char *S1, char *S2, int m, int n) ( int LCS_table(m + 1)(n + 1); // Building the mtrix in bottom-up way for (int i = 0; i <= m; i++) ( for (int j = 0; j <= n; j++) ( if (i == 0 || j == 0) LCS_table(i)(j) = 0; else if (S1(i - 1) == S2(j - 1)) LCS_table(i)(j) = LCS_table(i - 1)(j - 1) + 1; else LCS_table(i)(j) = max(LCS_table(i - 1)(j), LCS_table(i)(j - 1)); ) ) int index = LCS_table(m)(n); char lcsAlgo(index + 1); lcsAlgo(index) = ''; int i = m, j = n; while (i> 0 && j> 0) ( if (S1(i - 1) == S2(j - 1)) ( lcsAlgo(index - 1) = S1(i - 1); i--; j--; index--; ) else if (LCS_table(i - 1)(j)> LCS_table(i)(j - 1)) i--; else j--; ) // Printing the sub sequences cout << "S1 : " << S1 << "S2 : " << S2 << "LCS: " << lcsAlgo << ""; ) int main() ( char S1() = "ACADB"; char S2() = "CBDA"; int m = strlen(S1); int n = strlen(S2); lcsAlgo(S1, S2, m, n); )