A Longest Common Sub­se­quence (LCS) é um problema clássico da in­for­má­tica. As soluções para resolver o problema LCS aparecem fre­quen­te­mente em en­tre­vis­tas de pro­gra­ma­ção e cursos de al­go­rit­mos.

Em que consiste o problema da Longest Common Sub­se­quence?

O objetivo é encontrar a sub­seqüên­cia comum mais longa (“Longest Common Sub­se­quence”) de duas sequên­cias. Uma sub­seqüên­cia é derivada de uma sequência original. A sub­seqüên­cia tem a mesma ordem de elementos, mas alguns podem ter sido eli­mi­na­dos. Mostramos este princípio com alguns exemplos:

Sequência X Sequência Y LCS(X, Y)
FATHER VATER ATER
MOTHER MUTTER MTER
DAVID DANIEL DAI
Nota

Existe uma diferença im­por­tante entre a sub­seqüên­cia comum mais longa e a subcadeia comum mais longa (“longest common substring”). Uma subcadeia, ao contrário da sub­seqüên­cia, não pode conter espaços. Uti­li­zando o exemplo DANIEL, a sub­seqüên­cia comum mais longa seria “DA”, já que “I” é in­ter­rom­pida por “V” e “N”, res­pec­ti­va­mente.

Um exemplo prático do problema da LCS

O problema da Longest Common Sub­se­quence (LCS) é im­por­tante em todas as áreas em que se trabalha com sequên­cias derivadas umas das outras. As soluções para encontrar a LCS são uti­li­za­das, por exemplo, para examinar textos em busca de se­me­lhan­ças e di­fe­ren­ças. Desta forma, é possível detectar plágio. O conhecido uti­li­tá­rio «diff», que mostra as al­te­ra­ções em ficheiros de código-fonte, também se baseia no problema LCS.

Na bi­oin­for­má­tica, o problema da Longest Common Sub­se­quence é utilizado na análise de sequên­cias de ADN. As mutações alteram as bases do ADN em posições in­di­vi­du­ais ao longo do tempo. A presença de uma sequência comum mais longa entre duas sequên­cias indica um alto grau de pa­ren­tesco genético. Desta forma, é possível rastrear os avanços genéticos entre espécies ao longo da evolução.

Os lin­guis­tas utilizam o problema da Longest Common Sub­se­quence (Sequência Comum Mais Longa) para estudar a evolução das línguas ao longo dos séculos. Se forem en­con­tra­das duas palavras de línguas di­fe­ren­tes que tenham o mesmo sig­ni­fi­cado 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 cor­res­pon­dên­cia das letras.

Como funcionam as soluções para o problema da Longest Common Sub­se­quence?

O problema LCS pode ser resolvido, em primeiro lugar, com uma abordagem «ingénua», sem qualquer oti­mi­za­ção ou abordagem especial. De­ter­mi­nam-se todas as sub­seqüên­cias das duas sequên­cias e encontra-se a sequência mais longa que ambas têm em comum. Esta abordagem não é to­tal­mente eficiente e só é adequada para sequên­cias curtas.

A seguir, apre­sen­ta­mos três abor­da­gens mais efi­ci­en­tes para o problema LCS:

  1. Abordagem recursiva
  2. Oti­mi­za­ção por meio de me­moi­za­ção
  3. Pro­gra­ma­ção dinâmica

Todas as abor­da­gens têm em comum a distinção de três casos em relação a duas sequên­cias:

  • A última letra é igual
  • A última letra não é igual
  • O com­pri­mento de uma das sequên­cias é zero

As abor­da­gens diferem em com­ple­xi­dade temporal (tempo de execução as­sin­tó­tico) e espacial (re­qui­si­tos de memória):

Enfoque Tempo de execução Memória ne­ces­sá­ria
Abordagem ingênua O(n * n²) O(n)
Abordagem recursiva O(n²) O(1)
Oti­mi­za­ção por me­moi­za­ção O(n *m) O(n* m)
Pro­gra­ma­ção dinâmica O(n *m) O(n* m)
Nota

Cada um dos al­go­rit­mos apre­sen­ta­dos a seguir determina o com­pri­mento da sub­seqüên­cia comum mais longa. Pode haver várias sub­seqüên­cias es­pe­cí­fi­cas desse com­pri­mento que podem ser de­ter­mi­na­das por meio de outras etapas.

De­ter­mi­nar re­cur­si­va­mente a sequência comum mais longa

Ao examinar o problema LCS, fica evidente que ele tem uma “su­bes­tru­tura ótima”. Isso significa que o problema pode ser reduzido a sub­pro­ble­mas. Para encontrar a solução, uma abordagem recursiva é ideal. Mostramos a im­ple­men­ta­ção do algoritmo em três lin­gua­gens de pro­gra­ma­ção populares.

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

Oti­mi­za­ção da abordagem recursiva através da me­moi­za­ção

Uma análise mais detalhada da abordagem recursiva calcula sub­seqüên­cias so­bre­pos­tas. Essa pro­pri­e­dade, de­no­mi­nada “so­bre­po­si­ção de sub­pro­ble­mas”, é conhecida como sequência de Fibonacci. Também neste caso, as partes re­cur­si­vas são cal­cu­la­das re­pe­ti­da­mente para chegar à solução. Para tornar o processo mais eficiente, é muito prático utilizar a me­moi­za­ção. Em outras palavras, ar­ma­ze­na­mos em cache os sub­pro­ble­mas já cal­cu­la­dos em uma matriz bi­di­men­si­o­nal.

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)
{
    // 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;
}
c++

Pro­gra­ma­ção dinâmica da Longest Common Sub­se­quence

A pro­gra­ma­ção dinâmica é uma técnica não recursiva para resolver problemas de oti­mi­za­ção, dividindo-os em sub­pro­ble­mas menores e re­sol­vendo-os de baixo para cima. A pro­gra­ma­ção dinâmica é aplicada, entre outras coisas, como método de solução para al­go­rit­mos de path­fin­ding. O problema da Longest Common Sub­se­quence também pode ser resolvido através da pro­gra­ma­ção dinâmica, uti­li­zando uma matriz bi­di­men­si­o­nal.

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

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

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;
}
c++
Ir para o menu principal