# O problema da sequência comum mais longa

A Longest Common Subsequence (LCS) é um **problema clássico da informática**. As soluções para resolver o problema LCS aparecem frequentemente em entrevistas de programação e cursos de algoritmos.

## Em que consiste o problema da Longest Common Subsequence?

O objetivo é **encontrar a subseqüência comum mais longa** (“Longest Common Subsequence”) de duas sequências. Uma subseqüência é derivada de uma sequência original. A subseqüência tem a mesma ordem de elementos, mas alguns podem ter sido eliminados. Mostramos este princípio com alguns exemplos:

<table>
  <thead>
    <tr>
      <th>Sequência `X`</th>
      <th>Sequência `Y`</th>
      <th>`LCS(X, Y)`</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>`FATHER`</td>
      <td>`VATER`</td>
      <td>`ATER`</td>
    </tr>
    <tr>
      <td>`MOTHER`</td>
      <td>`MUTTER`</td>
      <td>`MTER`</td>
    </tr>
    <tr>
      <td>`DAVID`</td>
      <td>`DANIEL`</td>
      <td>`DAI`</td>
    </tr>
  </tbody>
</table>

Nota Existe uma **diferença importante entre a subseqüência comum mais longa e a subcadeia comum mais longa** (“longest common substring”). Uma subcadeia, ao contrário da subseqüência, não pode conter espaços. Utilizando o exemplo `DANIEL`, a subseqüência comum mais longa seria “DA”, já que “I” é interrompida por “V” e “N”, respectivamente.

## Um exemplo prático do problema da LCS

O problema da Longest Common Subsequence (LCS) é importante em **todas as áreas em que se trabalha com sequências derivadas umas das outras**. As soluções para encontrar a LCS são utilizadas, por exemplo, para examinar textos em busca de semelhanças e diferenças. Desta forma, é possível detectar plágio. O conhecido utilitário «diff», que mostra as alterações em ficheiros de código-fonte, também se baseia no problema LCS.

Na bioinformática, o problema da Longest Common Subsequence é utilizado na **análise de sequências de ADN**. As mutações alteram as bases do ADN em posições individuais ao longo do tempo. A presença de uma sequência comum mais longa entre duas sequências indica um alto grau de parentesco genético. Desta forma, é possível rastrear os avanços genéticos entre espécies ao longo da evolução.

Os linguistas utilizam o problema da Longest Common Subsequence (Sequência Comum Mais Longa) para estudar a **evolução das línguas ao longo dos séculos**. Se forem encontradas duas palavras de línguas diferentes que tenham o mesmo significado e partilhem uma sequência comum longa, isso indica uma origem comum. Desta forma, a evolução histórica pode ser deduzida a partir da correspondência das letras.

## Como funcionam as soluções para o problema da Longest Common Subsequence?

O problema LCS pode ser resolvido, em primeiro lugar, com uma abordagem «ingénua», sem qualquer otimização ou abordagem especial. Determinam-se todas as subseqüências das duas sequências e encontra-se **a sequência mais longa que ambas têm em comum**. Esta abordagem não é totalmente eficiente e só é adequada para sequências curtas.

A seguir, apresentamos três **abordagens mais eficientes** para o problema LCS:

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

Todas as **abordagens têm em comum** a distinção de três casos em relação a duas sequências:

- A última letra é igual
- A última letra não é igual
- O comprimento de uma das sequências é zero

As **abordagens diferem** em complexidade temporal (tempo de execução assintótico) e espacial (requisitos de memória):

<table>
  <thead>
    <tr>
      <th>Enfoque</th>
      <th>Tempo de execução</th>
      <th>Memória necessá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 por 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 Cada um dos algoritmos apresentados a seguir determina o comprimento da subseqüência comum mais longa. Pode haver várias subseqüências específicas desse comprimento que podem ser determinadas por meio de outras etapas.

### Determinar recursivamente a sequência comum mais longa

Ao examinar o problema LCS, fica evidente que ele tem uma “subestrutura ótima”. Isso significa que o **problema pode ser reduzido** a subproblemas. Para encontrar a solução, uma abordagem recursiva é ideal. Mostramos a implementação do algoritmo em três linguagens de programação populares.

#### 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 através da memoização

Uma análise mais detalhada da abordagem recursiva calcula subseqüências sobrepostas. Essa propriedade, denominada “sobreposição de subproblemas”, é conhecida como sequência de Fibonacci. Também neste caso, **as partes recursivas são calculadas repetidamente para chegar à solução**. Para tornar o processo mais eficiente, é muito prático utilizar a memoização. Em outras palavras, armazenamos em cache os subproblemas já calculados 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)
{
    // 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[m - 1] == Y[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] = max(lcs(X, Y, m, n - 1, table), lcs(X, Y, m - 1, n, table));
        return table;
    }
}
// Let's test
int main()
{
    // Initialize variables
    char X[] = "DAVID";
    char Y[] = "DANIEL";
    int m = strlen(X);
    int n = strlen(Y);
    // Initialize table with `-1`
    vector<vector<int>> table(m + 1, vector<int>(n + 1, -1));
    
    // Compute and output length of LCS
    cout << "Length of LCS is: " << lcs(X, Y, m, n, table);
    return 0;
}
```

### Programação dinâmica da Longest Common Subsequence

A programação dinâmica é uma técnica não recursiva para resolver problemas de otimização, dividindo-os em **subproblemas menores e resolvendo-os de baixo para cima**. A programação dinâmica é aplicada, entre outras coisas, como método de solução para algoritmos de [pathfinding](https://www.ionos.com/pt-pt/digitalguide/marketing-online/analise-da-web/pathfinding-busca-de-percursos-na-informatica/). O problema da Longest Common Subsequence também pode ser resolvido através da programação dinâmica, utilizando uma matriz bidimensional.

#### Python

```python
def lcs(X , Y, m, n): 
    
    # Initialize dynamic programming table fields to `None`
    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}")
```

#### Java

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

#### C++

```c++
#include <bits/stdc++.h>
using namespace std;
int lcs(string X, string Y, int m, int n) {
	// Initialize dynamic programming table
	int table[m + 1][n + 1];
	// Compute table values
	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[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
int main() {
  // Initialize variables
  string X = "DAVID";
  string Y = "DANIEL";
  int m = X.size();
  int n = Y.size();
  // Compute and output length of LCS
  cout << "Length of LCS is " << lcs(X, Y, m, n);
  return 0;
}
```


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