# Kas ir garākā kopīgā apakšsekvences problēma?

Garākās kopējās apakšsekvences (LCS) ir **tipiska problēma IT jomā**. LCS problēmas risināšanas pieejas bieži tiek izmantotas programmētāju intervijās un algoritmu kursos.

## Kāda ir garākā kopīgā apakšsekvence?

Mērķis ir **atrast garāko kopīgo apakšsekvenci** divās sekvencēs. Šeit apakšsekvence ir atvasināta no sekvences. Apakšsekvencei ir tāds pats elementu secības kārtība, dažos gadījumos, kad elementi tiek noņemti. Apskatīsim dažus piemērus, lai labāk izprastu šo principu:

<table>
  <thead>
    <tr>
      <th>Sekvence `X`</th>
      <th>Sekvence `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 Ir svarīga **atšķirība starp garāko kopīgo apakšsekvenci un garāko kopīgo apakšvirkni**, jo apakšvirknei var nebūt nekādu atstarpju. Piemērā ar vārdiem „DAVID” un „DANIEL” garākā kopīgā apakšvirkne būtu „DA”, jo „I” ir atdalīts ar „V” un „N”.

## Vai ir kādi praktiski piemēri par LCS problēmu?

Garākās kopējās apakšsekvences problēma ir svarīgs jautājums **visās jomās, kurās tiek izmantotas savstarpēji saistītas sekvences.** Ir noteikti veidi, kā atrast LCS, lai redzētu, vai pastāv līdzības vai atšķirības, un, savukārt, atklātu jebkādu plaģiātu. Pazīstamais rīks “diff”, kas pārbauda izmaiņas avota teksta failos, ir balstīts uz LCS problēmu.

Bioinformātikā garākās kopējās apakšsekvences problēma bieži tiek izmantota, **analizējot DNS sekvences**. DNS bāzes laika gaitā mainās noteiktās pozīcijās mutāciju dēļ. Garas kopējās apakšsekvences klātbūtne divās sekvencēs liecina par ģenētisku saistību. Tas ļauj mums izsekot sugu evolūciju, pateicoties ģenētiskajai attīstībai.

Lingvisti var izmantot garākās kopīgās apakšsekvences problēmu, lai pētītu **valodas attīstību gadsimtu gaitā**. Ja ir divi vārdi no dažādām valodām, kuriem ir vienāda nozīme un gara kopīga apakšsekvence, tas liecina, ka tiem ir vienāds sakne un etimoloģija. Tādā gadījumā to var uzskatīt par līdzīgu vēsturisko attīstību.

## Kādi ir risinājumi garākās kopējās apakšsekvences problēmai?

Pirmkārt, LCS problēmu var atrisināt ar **naivu pieeju**. Tā ir vienkārša pieeja, neizmantojot nekādas optimizācijas vai īpašas metodes. Lai to izdarītu, vienkārši aprēķina visas divu secību apakšsecības un atrod **garāko kopīgo apakšsecību**. Diemžēl šī pieeja nav ļoti efektīva un tādēļ ir piemērota tikai īsām secībām.

Zemāk atradīsiet trīs **efektīvus risinājumus** LCS problēmai:

1. Rekursīvā pieeja
2. Optimizācija ar memoisāciju
3. Dinamiskā programmēšana

Visām **pieejām ir kopīgs** tas, ka attiecībā uz abām secībām tās atšķiras trīs gadījumos:

- Pēdējā burta ir tāds pats.
- Pēdējā burta nav tāds pats.
- Vienas no secībām garums ir nulle.

**Katra pieeja atšķiras** ar savu laika sarežģītību (asimptotisko izpildes laiku) un telpas sarežģītību (atmiņas izmantošanu):

<table>
  <thead>
    <tr>
      <th>Pieeja</th>
      <th>Darba laiks</th>
      <th>Atmiņa</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>Naivā pieeja</td>
      <td>`O(n * n²)`</td>
      <td>`O(n)`</td>
    </tr>
    <tr>
      <td>Rekursīvā pieeja</td>
      <td>`O(n²)`</td>
      <td>`O(1)`</td>
    </tr>
    <tr>
      <td>Optimizācija ar memoisāciju</td>
      <td>`O(n  *m)`</td>
      <td>`O(n*  m)`</td>
    </tr>
    <tr>
      <td>Dinamiskā programmēšana</td>
      <td>`O(n  *m)`</td>
      <td>`O(n*  m)`</td>
    </tr>
  </tbody>
</table>

Note Zemāk izklāstītie algoritmi aprēķina garāko kopīgo apakšsekvenci. Ja piemērojams, ir vairākas šāda garuma apakšsekvences, kuras var noteikt, izmantojot citus soļus.

### Ilgākās kopējās apakšsekvences rekursīva noteikšana

Ja aplūkojat LCS problēmu, varat redzēt, ka tai ir „optimāla apakšstruktūra”. Tas nozīmē, ka **problēmu var sadalīt apakšproblēmās**. Kā risinājumu varat izmantot rekursīvu pieeju. Zemāk atrodami daži algoritmu piemēri, lai to īstenotu trīs visbiežāk lietotajās programmēšanas valodās.

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

### Rekursīvās pieejas optimizēšana, izmantojot memoizāciju

Atkal aplūkojot rekursīvo pieeju, var redzēt, ka tiek aprēķinātas pārklājošās daļas. Šīs īpašības, ko sauc par „pārklājošām apakšproblēmām”, ir pazīstamas no Fibonači sekvencēm. Arī šajā gadījumā **rekursīvās sekvences tiek nepārtraukti aprēķinātas, lai iegūtu risinājumu**. Lai padarītu procesu efektīvāku, ir vērts izmantot memoisāciju. Citiem vārdiem sakot, jūs varat kešēt apakšproblēmas, kas jau ir aprēķinātas divdimensionālā matricā.

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

### Dinamiskā programmēšana garākajai kopīgajai apakšsekvencijai

Dinamiskā programmēšana ir nerekursīvs veids, kā risināt optimizācijas problēmas, sadalot tās **mazākās apakšproblēmās un pēc tam risinot tās „no apakšas uz augšu”.** Cita starpā dinamiskā programmēšana tiek izmantota kā risinājums [ceļu meklēšanas](https://www.ionos.com/lv-lv/digitalguide/timekla-tiklosana-timek-internets-interneta-interneta-interneta-interneta-interneta-interneta-interneta-intern/timekla-analitika/celu-meklesana-informatika/) algoritmiem. Garākās kopējās apakšsekvences problēmu var risināt arī ar dinamiskās programmēšanas palīdzību, izmantojot divdimensionālu matricu.

#### 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/lv-lv/digitalguide/timekla-vietnes/timekla-izstrade/garaka-kopiga-apakssekvence/](https://www.ionos.com/lv-lv/digitalguide/timekla-vietnes/timekla-izstrade/garaka-kopiga-apakssekvence/) for AI/LLM consumption.