# Kaj je problem najdaljše skupne podzaporedja?

Najdaljše skupne podzaporedja (LCS) so **tipična težava v informatiki**. Pristopi k reševanju težave LCS se pogosto pojavljajo v intervjujih za programerje in na tečajih algoritmov.

## Katera je najdaljša skupna podzaporedje?

Cilj je **najti najdaljšo skupno podzaporedje** v dveh zaporedjih. Podzaporedje izhaja iz zaporedja. Podzaporedje ima enak elementarni red, v nekaterih primerih, ko so elementi odstranjeni. Poglejmo nekaj primerov, da bolje razumemo načelo:

<table>
  <thead>
    <tr>
      <th>Zaporedje `X`</th>
      <th>Zaporedje `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 Pomembna **razlika med najdaljšo skupno podzaporedje in najdaljšo skupno podvrstico** je, da podvrstica ne sme imeti vrzeli. V primeru »DAVID« in »DANIEL« bi bila najdaljša skupna podvrstica »DA«, saj je »I« ločeno z »V« in »N«.

## Ali obstajajo praktični primeri problema LCS?

Problem najdaljše skupne podzaporedja je pomemben v **vseh področjih, kjer se uporabljajo zaporedja, ki izhajajo drug iz drugega.** Obstajajo določeni načini za iskanje LCS, da se ugotovi, ali obstajajo podobnosti ali razlike, in s tem odkrije morebitno plagiatorstvo. Znani program „diff“, ki preverja spremembe v izvornih besedilnih datotekah, temelji na problemu LCS.

V bioinformatiki se problem najdaljše skupne podzaporedja pogosto uporablja pri **analizi zaporedij DNK**. DNK-osnove se sčasoma spreminjajo na določenih mestih zaradi mutacij. Navzočnost dolgega skupnega podzaporedja v dveh zaporedjih bi nakazovala genetsko sorodnost. To nam omogoča, da s pomočjo genetskega razvoja sledimo evoluciji med vrstami.

Jezikoslovci lahko problem najdaljše skupne podzaporedja uporabijo tudi za raziskovanje **jezikovnega razvoja skozi stoletja**. Če imate dve besedi iz različnih jezikov, ki imata enak pomen in dolgo skupno podzaporedje, to nakazuje, da imata enak koren in etimologijo. To bi se torej štelo za podoben zgodovinski razvoj.

## Kakšne so rešitve za problem najdaljše skupne podzaporedja?

Najprej lahko rešite problem LCS z **naivnim pristopom**. To je preprost pristop brez uporabe optimizacij ali posebnih metod. Za to preprosto izračunate vse podzaporedja iz dveh zaporedij in poiščete **najdaljše skupno podzaporedje**. Na žalost ta pristop ni zelo učinkovit in je zato primeren le za kratka zaporedja.

Spodaj boste našli tri **učinkovite rešitve** za problem LCS:

1. Rekurzivni pristop
2. Optimizacija z uporabo memorizacije
3. Dinamično programiranje

Vsi **pristopi imajo skupno to**, da se v zvezi z dvema zaporedjema razlikujejo v treh primerih:

- Zadnja črka je enaka.
- Zadnja črka ni enaka.
- Dolžina ene od zaporedij je nič.

**Pristopi se razlikujejo** po časovni kompleksnosti (asimptotični čas izvajanja) in prostorski kompleksnosti (uporaba pomnilnika):

<table>
  <thead>
    <tr>
      <th>Pristop</th>
      <th>Trajanje</th>
      <th>Pomnilnik</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>Naivni pristop</td>
      <td>`O(n * n²)`</td>
      <td>`O(n)`</td>
    </tr>
    <tr>
      <td>Rekurzivni pristop</td>
      <td>`O(n²)`</td>
      <td>`O(1)`</td>
    </tr>
    <tr>
      <td>Optimizacija prek memorizacije</td>
      <td>`O(n  *m)`</td>
      <td>`O(n*  m)`</td>
    </tr>
    <tr>
      <td>Dinamično programiranje</td>
      <td>`O(n  *m)`</td>
      <td>`O(n*  m)`</td>
    </tr>
  </tbody>
</table>

Note Vsi spodaj navedeni algoritmi izračunajo dolžino najdaljše skupne podzaporedja. Če je to primerno, obstaja več podzaporedij te dolžine, ki jih je mogoče določiti z drugimi koraki.

### Rekurzivno določanje najdaljše skupne podzaporedja

Če pogledate problem LCS, lahko vidite, da ima „optimalno podstrukturo“. To pomeni, da **se problem lahko zreducira na podprobleme**. Kot rešitev lahko uporabite rekurzivni pristop. Spodaj najdete nekaj primerov algoritmov za implementacijo tega v treh najpogostejših programskih jezikih.

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

### Optimizacija rekurzivnega pristopa z uporabo memoizacije

Če ponovno pogledamo rekurzivni pristop, lahko vidimo, da se prekrivajoči deli izračunajo. Te lastnosti, imenovane »prekrivajoči se podproblemi«, so znane iz Fibonaccijevih zaporedij. Tudi v tem primeru **se rekurzivna zaporedja nenehno izračunavajo za rešitev**. Da bi proces postal učinkovitejši, je smiselno uporabiti memoizacijo. Z drugimi besedami, podprobleme, ki so že bili izračunani, lahko shranite v dvodimenzionalni matrici.

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

### Dinamično programiranje za najdaljšo skupno podzaporedje

Dinamično programiranje je nerekurziven način reševanja optimizacijskih problemov, pri katerem **se** ti razdelijo na **manjše podprobleme in nato rešijo od spodaj navzgor.** Dinamično programiranje se med drugim uporablja kot rešitev za algoritme [iskanja poti](https://www.ionos.com/sl-si/digitalguide/spletno-trzenje/spletna-analitika/iskanje-poti-v-informatiki/). Problem najdaljše skupne podzaporedja se lahko reši tudi z dinamičnim programiranjem, če se uporabi dvodimenzionalna matrika.

#### 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/sl-si/digitalguide/spletne-strani/razvoj-spletnih-strani/najdaljsa-skupna-podzaporedja/](https://www.ionos.com/sl-si/digitalguide/spletne-strani/razvoj-spletnih-strani/najdaljsa-skupna-podzaporedja/) for AI/LLM consumption.