Qual é o problema da subsequência comum mais longa?

As mais longas subsequências comuns (LCS) são um problema típico em TI . As abordagens para resolver o problema LCS aparecem com frequência em entrevistas para programadores e cursos de algoritmos.

Qual é a mais longa subsequência comum?

O objetivo é encontrar a maior subsequência comum em duas sequências. É aqui que uma subsequência é derivada de uma sequência. A subsequência tem a mesma ordem elementar, em alguns casos, quando os elementos são removidos. Vamos dar uma olhada em alguns exemplos para ter uma ideia melhor do princípio:

Sequence X Sequence Y LCS(X, Y)
FATHER MATTER ATER
MOTHER HERBAL HER
DAVID DANIEL DAI
Nota

Há uma importante diferença entre a mais longa subsequência comum e a mais longa substring comum sendo que uma substring pode não ter lacunas. No exemplo de “DAVID” e “DANIEL”, a substring comum mais longa seria “DA”, pois “I” está separado por “V” e “N”.

Há algum exemplo prático do problema LCS?

O problema da mais longa subsequência comum é uma questão importante em todas as áreas em que são usadas sequências que se originam umas das outras. Existem algumas maneiras de encontrar LCS para verificar se há semelhanças ou diferenças e, por sua vez, descobrir qualquer plágio. O conhecido utilitário “diff”, que verifica se há alterações nos arquivos de texto de origem, baseia-se no problema de LCS.

Na bioinformática, o problema da mais longa subsequência comum é usado com frequência ao analisar sequências de DNA. As bases do DNA mudam em determinadas posições ao longo do tempo devido a mutações. A presença de uma longa subsequência comum em duas sequências sugere uma relação genética. Isso pode nos permitir reconstituir a evolução entre as espécies graças ao desenvolvimento genético.

Os linguistas também podem usar o problema da mais longa subsequência comum para pesquisar o desenvolvimento linguístico ao longo dos séculos. Se você tiver duas palavras de idiomas diferentes que tenham o mesmo significado e uma longa sequência comum, isso sugere que elas têm a mesma raiz e etimologia. Isso seria considerado, então, um desenvolvimento histórico semelhante.

Quais são as soluções para o problema da mais longa subsequência comum?

Em primeiro lugar, é possível resolver o problema da LCS com uma abordagem ingênua. Essa é uma abordagem simples, sem usar nenhuma otimização ou método especial. Para isso, basta computar todas as subsequências de duas sequências e encontrar a subsequência comum mais longa. Infelizmente, essa abordagem não é muito eficiente e, portanto, só é adequada para sequências curtas.

Abaixo você encontrará três soluções eficientes para o problema LCS:

  1. Abordagem recursiva
  2. Otimização por meio de memoização
  3. Programação dinâmica

O que todas as abordagens têm em comum é que, com relação às duas sequências, elas diferem em três casos:

  • A última letra é a mesma.
  • A última letra não é a mesma.
  • O comprimento de uma das sequências é zero.

As abordagens diferem em sua complexidade de tempo (tempo de execução assintótico) e complexidade de espaço (uso de memória):

Abordagem Tempo de execução Memória
Abordagem ingênua O(n * n²) O(n)
Abordagem recursiva O(n²) O(1)
Otimização via memoização O(n *m) O(n* m)
Programação dinâmica O(n *m) O(n* m)
Nota

Todos os algoritmos definidos abaixo calculam o comprimento da maior subsequência comum. Se for o caso, há vários conjuntos de subsequências com esse comprimento que podem ser determinados por meio de outras etapas.

Determinação recursiva da maior subsequência comum

Se você observar o problema LCS, verá que ele tem uma “subestrutura ideal”. Isso significa que o problema pode ser reduzido a subproblemas. Como solução, você pode usar uma abordagem recursiva. Abaixo, você encontrará alguns exemplos de algoritmos para implementar isso em três das linguagens de programação mais comuns.

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

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

Otimização da abordagem recursiva usando memoização

Ao analisar novamente a abordagem recursiva, você pode ver que as partes sobrepostas são computadas. Essas características, chamadas de “subproblemas sobrepostos”, são conhecidas das sequências de Fibonacci. Nesse caso também as sequências recursivas são constantemente computadas para obter uma solução. Para tornar o processo mais eficiente, vale a pena usar a memoização. Em outras palavras, você pode armazenar os subproblemas que já foram computados em uma 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)
{
  // Caso básico
  if (m == 0 || n == 0)
    return 0;
  // Valor já computado na posição determinada
  if (table[m][n] != -1) {
    return table[m][n];
  }
  // Os últimos elementos são iguais
  if (X[m - 1] == Y[n - 1]) {
    table[m][n] = 1 + lcs(X, Y, m - 1, n - 1, table);
    return table[m][n];
  }
  // Os últimos elementos são diferentes
  else {
    table[m][n] = max(lcs(X, Y, m, n - 1, table), lcs(X, Y, m - 1, n, table));
    return table;
  }
}
// Vamos testar
int main()
{
  // Inicializar variáveis
  char X[] = "DAVID";
  char Y[] = "DANIEL";
  int m = strlen(X);
  int n = strlen(Y);
  // Inicializar a tabela com `-1`
  vetor<vector<int>> tabela(m + 1, vetor<int>(n + 1, -1));
  
  // Calcular e gerar o comprimento do LCS
  cout << "Length of LCS is: " << lcs(X, Y, m, n, table);
  return 0;
}
@@UNIQID67fe5360db3900.54711701@@python
def lcs(X , Y, m, n): 
  
  # Initialize dynamic programming table fields to@@UNIQID67fe5360db3974.27748659@@
  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}")
@@UNIQID67fe5360db3bc5.16312818@@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);
  }
}
@@UNIQID67fe5360db3dc4.31299911@@c++
#include <bits/stdc++.h>
using namespace std;
int lcs(string X, string Y, int m, int n) {
	// Inicializar a tabela de programação dinâmica
	int table[m + 1][n + 1];
	// Calcular os valores da tabela
	for (int i = 0; i <= m; i++) {
		for (int j = 0; j <= n; j++) {
			// Caso básico
			if (i == 0 || j == 0)
				table[i][j] = 0;
			// Os últimos elementos são iguais
			else if (X[i - 1] == Y[j - 1])
				table[i][j] = table[i - 1][j - 1] + 1;
			// Os últimos elementos são diferentes
			else
				table[i][j] = max(table[i - 1][j], table[i][j - 1]);
		}
	}
	return table[m][n];
}
// Vamos testar
int main() {
  // Inicializar variáveis
  string X = "DAVID";
  string Y = "DANIEL";
  int m = X.size();
  int n = Y.size();
  // Calcular e gerar o comprimento do LCS
  cout << "O comprimento do LCS é " << lcs(X, Y, m, n);
  return 0;
}
c++
Este artigo foi útil?
Para melhorar a sua experiência, este site usa cookies. Ao acessar o nosso site, você concorda com nosso uso de cookies. Mais informações