# Il problema della massima sottosequenza comune

L’individuazione della massima sottosequenza comune (LCS, dall’inglese “Longest Common Subsequence”) è un **classico problema dell’informatica**. Nelle interviste ai programmatori, alle programmatrici e nei corsi sugli algoritmi ricorrono spesso approcci alla risoluzione del problema della LCS.

## Che cos’è il problema della massima sottosequenza comune?

L’obiettivo è **individuare la massima sottosequenza comune** (“Longest Common Subsequence”) di due sequenze. Una sottosequenza (“subsequence”) è ricavata da una sequenza originale. La sottosequenza contiene la stessa sequenza di elementi, alcuni dei quali sono però stati rimossi. È possibile descrivere il principio con alcuni esempi:

<table>
  <thead>
    <tr>
      <th>Sequenza `X`</th>
      <th>Sequenza `Y`</th>
      <th>`LCS(X, Y)`</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>`FATHER`</td>
      <td>`PADRE`</td>
      <td>`AER`</td>
    </tr>
    <tr>
      <td>`MOTHER`</td>
      <td>`MADRE`</td>
      <td>`MRE`</td>
    </tr>
    <tr>
      <td>`DAVIDE`</td>
      <td>`DANIELE`</td>
      <td>`DAIE`</td>
    </tr>
  </tbody>
</table>

N.B. Vi è un’importante **differenza tra la massima sottosequenza comune e la massima sottostringa comune** (“Longest Common Substring”). A differenza della sottosequenza, una sottostringa non può contenere spazi vuoti. Nell’esempio con `“DAVIDE”` / `“DANIELE”` la massima sottostringa comune sarebbe `“DA”`, poiché le sequenze sono interrotte prima delle `“I”` da `“V”` o `“N”`.

## Qual è un esempio pratico del problema della LCS?

Il problema della massima sottosequenza comune è importante in **tutti i campi in cui si lavora con sequenze che derivano le une dalle altre**. Gli approcci all’individuazione della LCS si utilizzano, ad esempio, per esaminare i testi alla ricerca di aspetti simili e differenze: in questo modo è possibile individuare un plagio. Anche la nota utility `diff`, che mostra le modifiche ai file di codice sorgente, si basa sul problema della LCS.

In bioinformatica, il problema della massima sottosequenza comune si incontra nell’**analisi delle sequenze di DNA**. Con il passare del tempo, le mutazioni provocano cambiamenti delle basi in singoli punti del DNA. La presenza di una lunga sottosequenza comune tra due sequenze è segno di un’elevata parentela genetica. In questo modo è possibile seguire gli sviluppi genetici tra le specie nel corso dell’evoluzione.

I linguisti sfruttano il problema della massima sottosequenza comune per studiare lo **sviluppo delle lingue nel corso dei secoli**. Se si individuano due parole in lingue diverse che hanno lo stesso significato e condividono una lunga sottosequenza comune, significa che condividono la loro origine. In questo modo è possibile dedurre lo sviluppo storico dalla corrispondenza delle lettere nelle parole.

## Come funzionano gli approcci per la soluzione al problema della massima sottosequenza comune?

Per prima cosa, è possibile risolvere il problema della LCS con un approccio “naive”. Si tratta dell’approccio più ovvio in assenza di ottimizzazioni o metodologie particolari. A tal fine si determinano tutte le sottosequenze contenute nelle due sequenze e si individua **la massima sottosequenza che le due sequenze hanno in comune**. Purtroppo, questo approccio non è efficiente ed è quindi adatto solo a sequenze brevi.

Nelle parti seguenti ti mostriamo tre **approcci efficienti per risolvere** il problema della LCS:

1. Approccio ricorsivo
2. Ottimizzazione tramite memoizzazione
3. Programmazione dinamica

Un **aspetto condiviso da tutti gli approcci** è che distinguono 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 differiscono** per complessità temporale (tempo di esecuzione asintotico) e complessità spaziale (requisiti di memoria):

<table>
  <thead>
    <tr>
      <th>Approccio</th>
      <th>Tempo esec.</th>
      <th>Req. memoria</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>Approccio naive</td>
      <td>`O(n * n²)`</td>
      <td>`O(n)`</td>
    </tr>
    <tr>
      <td>Approccio ricorsivo</td>
      <td>`O(n²)`</td>
      <td>`O(1)`</td>
    </tr>
    <tr>
      <td>Ottimizzazione tramite memoizzazione</td>
      <td>`O(n  *m)`</td>
      <td>`O(n*  m)`</td>
    </tr>
    <tr>
      <td>Programmazione dinamica</td>
      <td>`O(n  *m)`</td>
      <td>`O(n*  m)`</td>
    </tr>
  </tbody>
</table>

N.B. Ciascuno degli algoritmi seguenti determina la lunghezza della massima sottosequenza comune. Potrebbero essere presenti più sottosequenze effettive di questa lunghezza, che è possibile determinare mediante ulteriori passaggi.

### Rilevamento ricorsivo della massima sottosequenza comune

Osservando il problema della LCS si nota che presenta una “sottostruttura ottimale”. In pratica, il **problema è riducibile in sottoproblemi**. È quindi possibile utilizzare un approccio ricorsivo per risolvere questo problema. Nelle parti seguenti ti mostriamo l’implementazione dell’[algoritmo](https://www.ionos.it/digitalguide/online-marketing/analisi-web/cose-un-algoritmo/ "Cos’è un algoritmo?") in tre linguaggi di programmazione particolarmente diffusi.

#### 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 = "DANIELE", "DAVIDE"
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;
}
```

### Ottimizzazione dell’approccio ricorsivo tramite memoizzazione

Esaminando ulteriormente l’approccio ricorsivo si vede come porti al calcolo di sottosequenze sovrapposte. Questa caratteristica, che prende il nome di “sottoproblemi sovrapposti”, è nota sin dalla sequenza di Fibonacci. Anche in questo caso **le parti ricorsive vengono calcolate ripetutamente avvicinandosi alla soluzione**. Per rendere il processo più efficiente, è quindi opportuno utilizzare la memoizzazione. In altre parole, i sottoproblemi già calcolati vengono conservati in una cache a matrice bidimensionale.

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

#### 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[] = "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;
}
```

### La programmazione dinamica per la massima sottosequenza comune

La programmazione dinamica è una tecnica non ricorsiva che permette di risolvere i problemi di ottimizzazione suddividendoli in **sottoproblemi più piccoli e risolvendoli quindi con un approccio “bottom-up” (dal basso verso l’alto)**. La programmazione dinamica trova applicazione, ad esempio, come approccio agli algoritmi di [pathfinding](https://www.ionos.it/digitalguide/online-marketing/analisi-web/pathfinding-in-informatica/) per la ricerca dei percorsi. È possibile risolvere il problema della massima sottosequenza comune anche per mezzo della programmazione dinamica utilizzando una matrice bidimensionale.

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

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

#### 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 = "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;
}
```


This is a markdown version of: [https://www.ionos.it/digitalguide/siti-web/programmazione-del-sito-web/massima-sottosequenza-comune/](https://www.ionos.it/digitalguide/siti-web/programmazione-del-sito-web/massima-sottosequenza-comune/) for AI/LLM consumption.