# 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:

<table>
  <thead>
    <tr>
      <th>Sequence `X`</th>
      <th>Sequence `Y`</th>
      <th>`LCS(X, Y)`</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>`FATHER`</td>
      <td>`MATTER`</td>
      <td>`ATER`</td>
    </tr>
    <tr>
      <td>`MOTHER`</td>
      <td>`HERBAL`</td>
      <td>`HER`</td>
    </tr>
    <tr>
      <td>`DAVID`</td>
      <td>`DANIEL`</td>
      <td>`DAI`</td>
    </tr>
  </tbody>
</table>

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):

<table>
  <thead>
    <tr>
      <th>Abordagem</th>
      <th>Tempo de execução</th>
      <th>Memória</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>Abordagem ingênua</td>
      <td>`O(n * n²)`</td>
      <td>`O(n)`</td>
    </tr>
    <tr>
      <td>Abordagem recursiva</td>
      <td>`O(n²)`</td>
      <td>`O(1)`</td>
    </tr>
    <tr>
      <td>Otimização via memoização</td>
      <td>`O(n  *m)`</td>
      <td>`O(n*  m)`</td>
    </tr>
    <tr>
      <td>Programação dinâmica</td>
      <td>`O(n  *m)`</td>
      <td>`O(n*  m)`</td>
    </tr>
  </tbody>
</table>

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](https://www.ionos.com/pt-br/digitalguide/marketing-online/analise-web/o-que-e-algoritmo/) para implementar isso em três das linguagens de programação mais comuns.

#### Python

```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}")
```

#### Java

```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);
        }
}
```

#### C++

```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;
}
```

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

```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)}")
```

#### Java

```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);
    }
}
```

#### C++

```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;
}
```


This is a markdown version of: [https://www.ionos.com/pt-br/digitalguide/sites-de-internet/desenvolvimento-web/maior-sequencia-comum/](https://www.ionos.com/pt-br/digitalguide/sites-de-internet/desenvolvimento-web/maior-sequencia-comum/) for AI/LLM consumption.