L’in­di­vi­dua­zio­ne della massima sot­to­se­quen­za comune (LCS, dall’inglese “Longest Common Sub­se­quen­ce”) è un classico problema dell’in­for­ma­ti­ca. Nelle in­ter­vi­ste ai pro­gram­ma­to­ri, alle pro­gram­ma­tri­ci e nei corsi sugli algoritmi ricorrono spesso approcci alla ri­so­lu­zio­ne del problema della LCS.

Che cos’è il problema della massima sot­to­se­quen­za comune?

L’obiettivo è in­di­vi­dua­re la massima sot­to­se­quen­za comune (“Longest Common Sub­se­quen­ce”) di due sequenze. Una sot­to­se­quen­za (“sub­se­quen­ce”) è ricavata da una sequenza originale. La sot­to­se­quen­za contiene la stessa sequenza di elementi, alcuni dei quali sono però stati rimossi. È possibile de­scri­ve­re il principio con alcuni esempi:

Sequenza X Sequenza Y LCS(X, Y)
FATHER PADRE AER
MOTHER MADRE MRE
DAVIDE DANIELE DAIE
N.B.

Vi è un’im­por­tan­te dif­fe­ren­za tra la massima sot­to­se­quen­za comune e la massima sot­to­strin­ga comune (“Longest Common Substring”). A dif­fe­ren­za della sot­to­se­quen­za, una sot­to­strin­ga non può contenere spazi vuoti. Nell’esempio con “DAVIDE” / “DANIELE” la massima sot­to­strin­ga comune sarebbe “DA”, poiché le sequenze sono in­ter­rot­te prima delle “I” da “V” o “N”.

Qual è un esempio pratico del problema della LCS?

Il problema della massima sot­to­se­quen­za comune è im­por­tan­te in tutti i campi in cui si lavora con sequenze che derivano le une dalle altre. Gli approcci all’in­di­vi­dua­zio­ne della LCS si uti­liz­za­no, ad esempio, per esaminare i testi alla ricerca di aspetti simili e dif­fe­ren­ze: in questo modo è possibile in­di­vi­dua­re un plagio. Anche la nota utility diff, che mostra le modifiche ai file di codice sorgente, si basa sul problema della LCS.

In bio­in­for­ma­ti­ca, il problema della massima sot­to­se­quen­za comune si incontra nell’analisi delle sequenze di DNA. Con il passare del tempo, le mutazioni provocano cam­bia­men­ti delle basi in singoli punti del DNA. La presenza di una lunga sot­to­se­quen­za comune tra due sequenze è segno di un’elevata parentela genetica. In questo modo è possibile seguire gli sviluppi genetici tra le specie nel corso dell’evo­lu­zio­ne.

I linguisti sfruttano il problema della massima sot­to­se­quen­za comune per studiare lo sviluppo delle lingue nel corso dei secoli. Se si in­di­vi­dua­no due parole in lingue diverse che hanno lo stesso si­gni­fi­ca­to e con­di­vi­do­no una lunga sot­to­se­quen­za comune, significa che con­di­vi­do­no la loro origine. In questo modo è possibile dedurre lo sviluppo storico dalla cor­ri­spon­den­za delle lettere nelle parole.

Come fun­zio­na­no gli approcci per la soluzione al problema della massima sot­to­se­quen­za comune?

Per prima cosa, è possibile risolvere il problema della LCS con un approccio “naive”. Si tratta dell’approccio più ovvio in assenza di ot­ti­miz­za­zio­ni o me­to­do­lo­gie par­ti­co­la­ri. A tal fine si de­ter­mi­na­no tutte le sot­to­se­quen­ze contenute nelle due sequenze e si individua la massima sot­to­se­quen­za che le due sequenze hanno in comune. Purtroppo, questo approccio non è ef­fi­cien­te ed è quindi adatto solo a sequenze brevi.

Nelle parti seguenti ti mostriamo tre approcci ef­fi­cien­ti per risolvere il problema della LCS:

  1. Approccio ricorsivo
  2. Ot­ti­miz­za­zio­ne tramite me­moiz­za­zio­ne
  3. Pro­gram­ma­zio­ne dinamica

Un aspetto condiviso da tutti gli approcci è che di­stin­guo­no tre casi per quanto riguarda le due sequenze:

  • L’ultima lettera è uguale.
  • L’ultima lettera non è uguale.
  • La lunghezza di una sequenza è zero.

Gli approcci dif­fe­ri­sco­no per com­ples­si­tà temporale (tempo di ese­cu­zio­ne asin­to­ti­co) e com­ples­si­tà spaziale (requisiti di memoria):

Approccio Tempo esec. Req. memoria
Approccio naive O(n * n²) O(n)
Approccio ricorsivo O(n²) O(1)
Ot­ti­miz­za­zio­ne tramite me­moiz­za­zio­ne O(n * m) O(n * m)
Pro­gram­ma­zio­ne dinamica O(n * m) O(n * m)
N.B.

Ciascuno degli algoritmi seguenti determina la lunghezza della massima sot­to­se­quen­za comune. Po­treb­be­ro essere presenti più sot­to­se­quen­ze effettive di questa lunghezza, che è possibile de­ter­mi­na­re mediante ulteriori passaggi.

Ri­le­va­men­to ricorsivo della massima sot­to­se­quen­za comune

Os­ser­van­do il problema della LCS si nota che presenta una “sot­to­strut­tu­ra ottimale”. In pratica, il problema è ri­du­ci­bi­le in sot­to­pro­ble­mi. È quindi possibile uti­liz­za­re un approccio ricorsivo per risolvere questo problema. Nelle parti seguenti ti mostriamo l’im­ple­men­ta­zio­ne dell’algoritmo in tre linguaggi di pro­gram­ma­zio­ne par­ti­co­lar­men­te diffusi.

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 = "DANIELE", "DAVIDE"
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
IONOS GPT
Il tuo as­si­sten­te IA sovrano per una maggiore pro­dut­ti­vi­tà

Fai domande, crea contenuti, fai ricerche – in modo sicuro e senza limiti di chat con IONOS GPT. L'al­ter­na­ti­va sovrana e con­ve­nien­te a ChatGPT e simili.

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

Ot­ti­miz­za­zio­ne dell’approccio ricorsivo tramite me­moiz­za­zio­ne

Esa­mi­nan­do ul­te­rior­men­te l’approccio ricorsivo si vede come porti al calcolo di sot­to­se­quen­ze so­vrap­po­ste. Questa ca­rat­te­ri­sti­ca, che prende il nome di “sot­to­pro­ble­mi so­vrap­po­sti”, è nota sin dalla sequenza di Fibonacci. Anche in questo caso le parti ricorsive vengono calcolate ri­pe­tu­ta­men­te av­vi­ci­nan­do­si alla soluzione. Per rendere il processo più ef­fi­cien­te, è quindi opportuno uti­liz­za­re la me­moiz­za­zio­ne. In altre parole, i sot­to­pro­ble­mi già calcolati vengono con­ser­va­ti in una cache a matrice bi­di­men­sio­na­le.

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 = "DAVIDE"
Y = "DANIELE"
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[m][n];
  }
}

// Let's test
int main()
{
  // Initialize variables
  char X[] = "DAVIDE";
  char Y[] = "DANIELE";
  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;
}
cpp

La pro­gram­ma­zio­ne dinamica per la massima sot­to­se­quen­za comune

La pro­gram­ma­zio­ne dinamica è una tecnica non ricorsiva che permette di risolvere i problemi di ot­ti­miz­za­zio­ne sud­di­vi­den­do­li in sot­to­pro­ble­mi più piccoli e ri­sol­ven­do­li quindi con un approccio “bottom-up” (dal basso verso l’alto). La pro­gram­ma­zio­ne dinamica trova ap­pli­ca­zio­ne, ad esempio, come approccio agli algoritmi di pa­th­fin­ding per la ricerca dei percorsi. È possibile risolvere il problema della massima sot­to­se­quen­za comune anche per mezzo della pro­gram­ma­zio­ne dinamica uti­liz­zan­do una matrice bi­di­men­sio­na­le.

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 = "DAVIDE"
Y = "DANIELE"

# 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 = "DAVIDE";
    String Y = "DANIELE";
    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 = "DAVIDE";
  string Y = "DANIELE";
  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;
}
cpp
Vai al menu prin­ci­pa­le