# Hvad er problemet med den længste fælles delsekvens?

Længste fælles delsekvenser (LCS) er et **typisk problem inden for IT**. Tilgange til løsning af LCS-problemet optræder ofte i interviews med programmører og på algoritmekurser.

## Hvad er den længste fælles delsekvens?

Målet er at **finde den længste fælles delsekvens** i to sekvenser. Her stammer en delsekvens fra en sekvens. Delsekvensen har samme elementære rækkefølge, i nogle tilfælde når elementer fjernes. Lad os se på nogle eksempler for at få en bedre forståelse af princippet:

<table>
  <thead>
    <tr>
      <th>Sekvens `X`</th>
      <th>Sekvens `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>

Note Der er en vigtig **forskel mellem den længste fælles delsekvens og den længste fælles delstreng**, idet en delstreng ikke må have mellemrum. I eksemplet med ‘DAVID’ og ‘DANIEL’ ville den længste fælles delstreng være ‘DA’, da ‘I’ er adskilt af ‘V’ og ‘N’.

## Er der nogen praktiske eksempler på LCS-problemet?

Problemet med den længste fælles delsekvens er et vigtigt emne inden **for alle områder, hvor der anvendes sekvenser, der stammer fra hinanden.** Der findes visse metoder til at finde LCS for at se, om der er ligheder eller forskelle, og dermed afsløre eventuel plagiering. Det velkendte værktøj ‘diff’, der kontrollerer for ændringer i kildetekstfiler, er baseret på LCS-problemet.

I bioinformatik bruges problemet med den længste fælles delsekvens ofte til **analyse af DNA-sekvenser**. DNA-baser ændrer sig med tiden på bestemte positioner på grund af mutationer. Tilstedeværelsen af en lang fælles delsekvens i to sekvenser tyder på et genetisk slægtskab. Dette gør det muligt for os at spore evolutionen mellem arter takket være den genetiske udvikling.

Sprogforskere kan også bruge problemet med den længste fælles delsekvens til at undersøge **sproglig udvikling gennem århundreder**. Hvis man har to ord fra forskellige sprog, som har samme betydning og en lang fælles delsekvens, tyder det på, at de har samme rod og etymologi. Dette vil så blive betragtet som en lignende historisk udvikling.

## Hvad er løsningerne på problemet med den længste fælles delsekvens?

Først og fremmest kan du løse LCS-problemet med en **naiv tilgang**. Dette er en enkel tilgang uden brug af optimeringer eller specielle metoder. For at gøre dette beregner du blot alle delsekvenser fra to sekvenser og finder den **længste fælles delsekvens**. Desværre er denne tilgang ikke særlig effektiv og er derfor kun egnet til korte sekvenser.

Nedenfor finder du tre **effektive løsninger** på LCS-problemet:

1. Rekursiv tilgang
2. Optimering gennem memoisation
3. Dynamisk programmering

**Fælles for** alle **tilgange er**, at de med hensyn til de to sekvenser adskiller sig i tre tilfælde:

- Det sidste bogstav er det samme.
- Det sidste bogstav er ikke det samme.
- En af sekvensernes længde er nul.

De **forskellige tilgange adskiller sig fra hinanden** med hensyn til tidskompleksitet (asymptotisk køretid) og rumkompleksitet (hukommelsesforbrug):

<table>
  <thead>
    <tr>
      <th>Tilgang</th>
      <th>Køretid</th>
      <th>Hukommelse</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>Naiv tilgang</td>
      <td>`O(n * n²)`</td>
      <td>`O(n)`</td>
    </tr>
    <tr>
      <td>Rekursiv tilgang</td>
      <td>`O(n²)`</td>
      <td>`O(1)`</td>
    </tr>
    <tr>
      <td>Optimering via memoisation</td>
      <td>`O(n  *m)`</td>
      <td>`O(n*  m)`</td>
    </tr>
    <tr>
      <td>Dynamisk programmering</td>
      <td>`O(n  *m)`</td>
      <td>`O(n*  m)`</td>
    </tr>
  </tbody>
</table>

Note Nedenstående algoritmer beregner alle længden af den længste fælles delsekvens. Der er, hvis det er relevant, flere delsekvenser af denne længde, som kan bestemmes ved hjælp af andre trin.

### Rekursiv bestemmelse af den længste fælles delsekvens

Hvis man ser på LCS-problemet, kan man se, at det har en ‘optimal understruktur’. Det betyder, at **problemet kan reduceres til delproblemer**. Som løsning kan man bruge en rekursiv tilgang. Nedenfor finder du nogle eksempler på algoritmer til at implementere dette i tre af de mest almindelige programmeringssprog.

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

### Optimering af den rekursive tilgang ved hjælp af memoisation

Når man ser på den rekursive tilgang igen, kan man se, at de overlappende dele beregnes. Disse karakteristika, kaldet ‘overlappende delproblemer’, er kendt fra Fibonacci-sekvenser. Også i dette tilfælde **beregnes rekursive sekvenser konstant for at finde en løsning**. For at gøre processen mere effektiv er det en god idé at bruge memoisation. Med andre ord kan man cache de delproblemer, der allerede er beregnet, i en todimensional matrix.

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

### Dynamisk programmering for den længste fælles delsekvens

Dynamisk programmering er en ikke-rekursiv metode til at løse optimeringsproblemer ved at opdele dem i **mindre delproblemer og derefter løse dem ‘nedenfra og op’.** Dynamisk programmering anvendes blandt andet som en løsning til [stifindingsalgoritmer](https://www.ionos.com/da-dk/digitalguide/online-markedsfoering/webanalyse/banebrydende-forskning-inden-for-informatik/). Problemet med den længste fælles delsekvens kan også løses ved hjælp af dynamisk programmering, når der anvendes en todimensional matrix.

#### 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/da-dk/digitalguide/websteder/webudvikling/laengste-faelles-delsekvens/](https://www.ionos.com/da-dk/digitalguide/websteder/webudvikling/laengste-faelles-delsekvens/) for AI/LLM consumption.