Subsequência Comum Mais Longa

Neste tutorial, você aprenderá como a maior subsequência comum é encontrada. Além disso, você encontrará exemplos de trabalho da subseqüência comum mais longa em C, C ++, Java e Python.

A maior subsequência comum (LCS) é definida como a maior subsequência comum a todas as sequências fornecidas, desde que os elementos da subsequência não sejam obrigados a ocupar posições consecutivas dentro das sequências originais.

Se S1 e S2 são as duas sequências fornecidas, então, Z é a subsequência comum de S1 e S2 se Z é uma subsequência de S1 e S2. Além disso, Z deve ser uma sequência estritamente crescente dos índices de S1 e S2.

Em uma sequência estritamente crescente, os índices dos elementos escolhidos nas sequências originais devem estar em ordem crescente em Z.

E se

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

Então, (A, D, B)não pode ser uma subsequência de S1, pois a ordem dos elementos não é a mesma (ou seja, sequência não estritamente crescente).

Vamos entender o LCS com um exemplo.

E se

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

Então, subseqüências comuns são (B, C), (C, D, A, C), (D, A, C), (A, A, C), (A, C), (C, D), …

Entre essas subsequências, (C, D, A, C)está a maior subsequência comum. Nós vamos encontrar esta subseqüência comum mais longa usando programação dinâmica.

Antes de prosseguir, se você ainda não conhece a programação dinâmica, consulte a programação dinâmica.

Usando programação dinâmica para encontrar o LCS

Tomemos duas sequências:

A primeira sequência,

segunda sequência

As etapas a seguir são seguidas para encontrar a maior subsequência comum.

Crie uma tabela de dimensões n+1*m+1onde n e m são os comprimentos de X e Y respectivamente. A primeira linha e a primeira coluna são preenchidas com zeros. Inicializar uma mesa
Preencha cada célula da tabela usando a seguinte lógica.
Se o caractere que corresponde à linha e coluna atuais corresponderem, preencha a célula atual adicionando um ao elemento diagonal. Aponte uma seta para a célula diagonal.
Caso contrário, pegue o valor máximo da coluna anterior e o elemento da linha anterior para preencher a célula atual. Aponte uma seta para a célula com valor máximo. Se eles forem iguais, aponte para qualquer um deles. Preencha os valores
A etapa 2 é repetida até que a tabela seja preenchida. Preencha todos os valores
O valor na última linha e na última coluna é o comprimento da maior subsequência comum. O canto inferior direito é o comprimento do LCS
Para encontrar a subsequência comum mais longa, comece a partir do último elemento e siga a direção da seta. Os elementos correspondentes ao símbolo () formam a subsequência comum mais longa. Crie um caminho de acordo com as setas

Portanto, a maior subsequência comum é CD.

LCS

Como um algoritmo de programação dinâmica é mais eficiente do que o algoritmo recursivo ao resolver um problema LCS?

O método de programação dinâmica reduz o número de chamadas de função. Ele armazena o resultado de cada chamada de função para que possa ser usado em chamadas futuras sem a necessidade de chamadas redundantes.

No algoritmo dinâmico acima, os resultados obtidos em cada comparação entre os elementos de X e os elementos de Y são armazenados em uma tabela para que possam ser usados em cálculos futuros.

Portanto, o tempo gasto por uma abordagem dinâmica é o tempo gasto para preencher a tabela (ou seja, O (mn)). Enquanto que o algoritmo de recursão tem a complexidade de 2 ^{máx (m, n)} .

Algoritmo de subseqüência comum mais longo

 X e Y são duas sequências dadas Inicializar uma tabela LCS de dimensão X.comprimento * Y.comprimento X. etiqueta = X Y. etiqueta = Y LCS (0) () = 0 LCS () (0) = 0 Iniciar a partir de LCS ( 1) (1) Compare X (i) e Y (j) Se X (i) = Y (j) LCS (i) (j) = 1 + LCS (i-1, j-1) Aponte uma seta para LCS (i) (j) Else LCS (i) (j) = max (LCS (i-1) (j), LCS (i) (j-1)) Aponte uma seta para max (LCS (i-1) ( j), LCS (i) (j-1))

Exemplos de Python, Java e 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); )