Langste ge­meen­schap­pe­lij­ke sub­reek­sen (LCS) zijn een typisch probleem in de IT. Be­na­de­rin­gen om het LCS-probleem op te lossen komen vaak voor in sol­li­ci­ta­tie­ge­sprek­ken voor pro­gram­meurs en al­go­rit­me­cur­sus­sen.

Wat is de langste ge­meen­schap­pe­lij­ke deelreeks?

Het doel is om de langste ge­meen­schap­pe­lij­ke deelreeks in twee reeksen te vinden. Hierbij wordt een deelreeks afgeleid van een reeks. De deelreeks heeft dezelfde ele­men­tai­re volgorde, in sommige gevallen wanneer elementen worden ver­wij­derd. Laten we enkele voor­beel­den bekijken om een beter beeld te krijgen van het principe:

Sequentie X Sequentie Y LCS(X, Y)
FATHER MATTER ATER
MOTHER HERBAL HER
DAVID DANIEL DAI
Opmerking

Er is een be­lang­rijk verschil tussen de langste ge­meen­schap­pe­lij­ke deelreeks en de langste ge­meen­schap­pe­lij­ke deel­string, namelijk dat een deel­string geen hiaten mag bevatten. In het voorbeeld van ‘DAVID’ en ‘DANIEL’ zou de langste ge­meen­schap­pe­lij­ke deel­string ‘DA’ zijn, aangezien ‘I’ wordt ge­schei­den door ‘V’ en ‘N’.

Zijn er prak­ti­sche voor­beel­den van het LCS-probleem?

Het probleem van de langste ge­meen­schap­pe­lij­ke deelreeks is een be­lang­rij­ke kwestie op alle gebieden waar reeksen worden gebruikt die uit elkaar voort­ko­men. Er zijn bepaalde manieren om LCS te vinden om te zien of er over­een­kom­sten of ver­schil­len zijn en zo eventueel plagiaat te ontdekken. Het bekende hulp­pro­gram­ma ‘diff’, dat con­tro­leert op wij­zi­gin­gen in bron­tekst­be­stan­den, is gebaseerd op het LCS-probleem.

In de bio-in­for­ma­ti­ca wordt het probleem van de langste ge­meen­schap­pe­lij­ke subreeks vaak gebruikt bij het ana­ly­se­ren van DNA-reeksen. DNA-basen ver­an­de­ren in de loop van de tijd op bepaalde posities als gevolg van mutaties. De aan­we­zig­heid van een lange ge­meen­schap­pe­lij­ke subreeks in twee reeksen zou wijzen op een ge­ne­ti­sche ver­want­schap. Hierdoor kunnen we dankzij de ge­ne­ti­sche ont­wik­ke­ling de evolutie tussen soorten te­rug­vol­gen.

Taal­kun­di­gen kunnen het probleem van de langste ge­meen­schap­pe­lij­ke deelreeks ook gebruiken om de taal­kun­di­ge ont­wik­ke­ling door de eeuwen heen te on­der­zoe­ken. Als je twee woorden uit ver­schil­len­de talen hebt die dezelfde betekenis hebben en een lange ge­meen­schap­pe­lij­ke deelreeks, dan sug­ge­reert dit dat ze dezelfde oorsprong en ety­mo­lo­gie hebben. Dit zou dan worden beschouwd als een ver­ge­lijk­ba­re his­to­ri­sche ont­wik­ke­ling.

Wat zijn de op­los­sin­gen voor het probleem van de langste ge­meen­schap­pe­lij­ke deelreeks?

Al­ler­eerst kun je het LCS-probleem oplossen met een naïeve aanpak. Dit is een een­vou­di­ge aanpak zonder gebruik te maken van op­ti­ma­li­sa­ties of speciale methoden. Hiervoor bereken je simpelweg alle sub­reek­sen van twee reeksen en zoek je de langste ge­meen­schap­pe­lij­ke subreeks. Helaas is deze aanpak niet erg efficiënt en daarom alleen geschikt voor korte reeksen.

Hieronder vindt u drie ef­fi­ci­ën­te op­los­sin­gen voor het LCS-probleem:

  1. Re­cur­sie­ve be­na­de­ring
  2. Op­ti­ma­li­sa­tie door middel van me­mo­ï­za­tie
  3. Dynamisch pro­gram­me­ren

Wat alle be­na­de­rin­gen gemeen hebben, is dat ze met be­trek­king tot de twee reeksen in drie gevallen van elkaar ver­schil­len:

  • De laatste letter is hetzelfde.
  • De laatste letter is niet hetzelfde.
  • De lengte van een van de reeksen is nul.

De be­na­de­rin­gen ver­schil­len onderling in hun tijd­com­plexi­teit (asymp­to­ti­sche looptijd) en ruimte­com­plexi­teit (ge­heu­gen­ge­bruik):

Aanpak Looptijd Geheugen
Naïeve aanpak O(n * n²) O(n)
Re­cur­sie­ve be­na­de­ring O(n²) O(1)
Op­ti­ma­li­sa­tie via me­mo­ï­za­tie O(n * m) O(n * m)
Dynamisch pro­gram­me­ren O(n * m) O(n * m)
Opmerking

De hieronder be­schre­ven al­go­rit­men berekenen allemaal de lengte van de langste ge­meen­schap­pe­lij­ke subreeks. Er zijn, indien van toe­pas­sing, meerdere vaste sub­reek­sen van deze lengte die met behulp van andere stappen kunnen worden bepaald.

Re­cur­sie­ve bepaling van de langste ge­meen­schap­pe­lij­ke deelreeks

Als je naar het LCS-probleem kijkt, zie je dat het een ‘optimale sub­struc­tuur’ heeft. Dit betekent dat het probleem kan worden te­rug­ge­bracht tot deel­pro­ble­men. Als oplossing kun je een re­cur­sie­ve be­na­de­ring gebruiken. Hieronder vind je enkele voor­beel­den van al­go­rit­men om dit in drie van de meest gangbare pro­gram­meer­ta­len te im­ple­men­te­ren.

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;
}
cpp

Op­ti­ma­li­se­ren van de re­cur­sie­ve be­na­de­ring met behulp van me­moi­sa­ti­on

Als je nog eens naar de re­cur­sie­ve be­na­de­ring kijkt, zie je dat de over­lap­pen­de delen worden berekend. Deze kenmerken, ‘over­lap­pen­de sub­pro­ble­men’ genoemd, zijn bekend uit Fibonacci-reeksen. Ook in dit geval worden voort­du­rend re­cur­sie­ve reeksen berekend om tot een oplossing te komen. Om het proces ef­fi­ci­ën­ter te maken, is het de moeite waard om me­moi­sa­ti­on te gebruiken. Met andere woorden, je kunt de sub­pro­ble­men die al zijn berekend, in een twee­di­men­si­o­na­le matrix in de cache opslaan.

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;
}
cpp

Dy­na­mi­sche pro­gram­me­ring voor de langste ge­meen­schap­pe­lij­ke deelreeks

Dynamisch pro­gram­me­ren is een niet-re­cur­sie­ve manier om op­ti­ma­li­sa­tie­pro­ble­men op te lossen door ze op te splitsen in kleinere deel­pro­ble­men en deze ver­vol­gens ‘bottom-up’ op te lossen. Dynamisch pro­gram­me­ren wordt onder andere toegepast als oplossing voor pa­thfin­ding-al­go­rit­men. Het probleem van de langste ge­meen­schap­pe­lij­ke deelreeks kan ook worden opgelost met behulp van dynamisch pro­gram­me­ren wanneer een twee­di­men­si­o­na­le matrix wordt gebruikt.

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;
}
cpp
Ga naar hoofdmenu