Najdaljše skupne pod­za­po­red­ja (LCS) so tipična težava v in­for­ma­ti­ki. Pristopi k reševanju težave LCS se pogosto po­ja­vlja­jo v in­ter­vju­jih za pro­gra­mer­je in na tečajih al­go­rit­mov.

Katera je najdaljša skupna pod­za­po­red­je?

Cilj je najti najdaljšo skupno pod­za­po­red­je v dveh za­po­red­jih. Pod­za­po­red­je izhaja iz zaporedja. Pod­za­po­red­je ima enak ele­men­tar­ni red, v nekaterih primerih, ko so elementi od­stra­nje­ni. Poglejmo nekaj primerov, da bolje razumemo načelo:

Zaporedje X Zaporedje Y LCS(X, Y)
FATHER MATTER ATER
MOTHER HERBAL HER
DAVID DANIEL DAI
Note

Pomembna razlika med najdaljšo skupno pod­za­po­red­je in najdaljšo skupno pod­vr­sti­co je, da pod­vr­sti­ca ne sme imeti vrzeli. V primeru »DAVID« in »DANIEL« bi bila najdaljša skupna pod­vr­sti­ca »DA«, saj je »I« ločeno z »V« in »N«.

Ali obstajajo praktični primeri problema LCS?

Problem najdaljše skupne pod­za­po­red­ja je pomemben v vseh področjih, kjer se upo­ra­blja­jo zaporedja, ki izhajajo drug iz drugega. Obstajajo določeni načini za iskanje LCS, da se ugotovi, ali obstajajo po­dob­no­sti ali razlike, in s tem odkrije morebitno pla­gi­a­tor­stvo. Znani program „diff“, ki preverja spremembe v izvornih be­se­dil­nih datotekah, temelji na problemu LCS.

V bi­o­in­for­ma­ti­ki se problem najdaljše skupne pod­za­po­red­ja pogosto uporablja pri analizi zaporedij DNK. DNK-osnove se sčasoma spre­mi­nja­jo na določenih mestih zaradi mutacij. Nav­zoč­nost dolgega skupnega pod­za­po­red­ja v dveh za­po­red­jih bi na­ka­zo­va­la genetsko sorodnost. To nam omogoča, da s pomočjo ge­net­ske­ga razvoja sledimo evoluciji med vrstami.

Je­zi­ko­slov­ci lahko problem najdaljše skupne pod­za­po­red­ja uporabijo tudi za raz­i­sko­va­nje je­zi­kov­ne­ga razvoja skozi stoletja. Če imate dve besedi iz različnih jezikov, ki imata enak pomen in dolgo skupno pod­za­po­red­je, to nakazuje, da imata enak koren in eti­mo­lo­gi­jo. To bi se torej štelo za podoben zgo­do­vin­ski razvoj.

Kakšne so rešitve za problem najdaljše skupne pod­za­po­red­ja?

Najprej lahko rešite problem LCS z naivnim pristopom. To je preprost pristop brez uporabe op­ti­mi­za­cij ali posebnih metod. Za to preprosto iz­ra­ču­na­te vse pod­za­po­red­ja iz dveh zaporedij in poiščete najdaljše skupno pod­za­po­red­je. Na žalost ta pristop ni zelo učinkovit in je zato primeren le za kratka zaporedja.

Spodaj boste našli tri učin­ko­vi­te rešitve za problem LCS:

  1. Re­kur­ziv­ni pristop
  2. Op­ti­mi­za­ci­ja z uporabo me­mo­ri­za­ci­je
  3. Dinamično pro­gra­mi­ra­nje

Vsi pristopi imajo skupno to, da se v zvezi z dvema za­po­red­je­ma raz­li­ku­je­jo v treh primerih:

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

Pristopi se raz­li­ku­je­jo po časovni kom­ple­ksno­sti (asimp­to­tič­ni čas izvajanja) in pro­stor­ski kom­ple­ksno­sti (uporaba po­mnil­ni­ka):

Pristop Trajanje Pomnilnik
Naivni pristop O(n * n²) O(n)
Re­kur­ziv­ni pristop O(n²) O(1)
Op­ti­mi­za­ci­ja prek me­mo­ri­za­ci­je O(n *m) O(n* m)
Dinamično pro­gra­mi­ra­nje O(n *m) O(n* m)
Note

Vsi spodaj navedeni algoritmi iz­ra­ču­na­jo dolžino najdaljše skupne pod­za­po­red­ja. Če je to primerno, obstaja več pod­za­po­re­dij te dolžine, ki jih je mogoče določiti z drugimi koraki.

Re­kur­ziv­no določanje najdaljše skupne pod­za­po­red­ja

Če pogledate problem LCS, lahko vidite, da ima „optimalno pod­struk­tu­ro“. To pomeni, da se problem lahko zreducira na pod­pro­ble­me. Kot rešitev lahko uporabite re­kur­ziv­ni pristop. Spodaj najdete nekaj primerov al­go­rit­mov za im­ple­men­ta­ci­jo tega v treh naj­po­go­stej­ših pro­gram­skih jezikih.

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}")
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

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;
}
c++

Op­ti­mi­za­ci­ja re­kur­ziv­ne­ga pristopa z uporabo me­mo­i­za­ci­je

Če ponovno pogledamo re­kur­ziv­ni pristop, lahko vidimo, da se pre­kri­va­jo­či deli iz­ra­ču­na­jo. Te lastnosti, imenovane »pre­kri­va­jo­či se pod­pro­ble­mi«, so znane iz Fi­bo­nac­ci­je­vih zaporedij. Tudi v tem primeru se re­kur­ziv­na zaporedja nenehno iz­ra­ču­na­va­jo za rešitev. Da bi proces postal učin­ko­vi­tej­ši, je smiselno uporabiti me­mo­i­za­ci­jo. Z drugimi besedami, pod­pro­ble­me, ki so že bili iz­ra­ču­na­ni, lahko shranite v dvo­di­men­zi­o­nal­ni matrici.

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)}")
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;
    }
}
// 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;
}
c++

Dinamično pro­gra­mi­ra­nje za najdaljšo skupno pod­za­po­red­je

Dinamično pro­gra­mi­ra­nje je ne­re­kur­zi­ven način reševanja op­ti­mi­za­cij­skih problemov, pri katerem se ti razdelijo na manjše pod­pro­ble­me in nato rešijo od spodaj navzgor. Dinamično pro­gra­mi­ra­nje se med drugim uporablja kot rešitev za algoritme iskanja poti. Problem najdaljše skupne pod­za­po­red­ja se lahko reši tudi z di­na­mič­nim pro­gra­mi­ra­njem, če se uporabi dvo­di­men­zi­o­nal­na matrika.

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}")
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 = "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);
    }
}
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 = "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;
}
c++
Go to Main Menu