NEJDELŠÍ SPOLEČNÁ PODSEKVENCE (LCS) - TECHCODEVIEW.COM

Vzhledem ke dvěma strunám, S1 a S2 , úkolem je najít délku nejdelší společné podsekvence, tedy nejdelší podsekvence přítomné v obou řetězcích.

zdarma vs zdarma

A nejdelší společná podsekvence (LCS) je definována jako nejdelší podsekvence, která je společná pro všechny dané vstupní sekvence.

Nejdelší společná posloupnost

Příklady:

Vstup: S1 = ABC, S2 = ACD
Výstup: 2
Vysvětlení: Nejdelší podsekvence, která je přítomna v obou řetězcích, je AC.

Vstup: S1 = AGGTAB, S2 = GXTXAYB
Výstup: 4
Vysvětlení: Nejdelší společná podsekvence je GTAB.

Vstup: S1 = ABC, S2 = CBA
Výstup: 1
Vysvětlení: Existují tři společné podposloupnosti délky 1, A, B a C a žádná společná podsekvence delší než 1.

Vstup: S1 = XYZW, S2 = XYWZ
Výstup: 3
Vysvětlení: Existují dvě společné podsekvence délky 3 XYZ a XYW a žádná společná podsekvence. o délce více než 3.

Doporučená praxe Nejdelší běžná následná sekvence Zkuste to!

Nejdelší společná podsekvence (LCS) pomocí rekurze:

Vygenerujte všechny možné podsekvence a najděte z nich nejdelší, který je přítomen v obou řetězcích pomocí Při realizaci nápadu postupujte podle následujících kroků:

Vytvořte rekurzivní funkci [řekněme lcs() ].
Zkontrolujte vztah mezi prvními znaky řetězců, které ještě nejsou zpracovány.
- V závislosti na vztahu zavolejte další rekurzivní funkci, jak je uvedeno výše.
Vraťte délku přijatého LCS jako odpověď.

Níže je uvedena implementace rekurzivního přístupu:

C++

 // A Naive recursive implementation of LCS problem #include  using namespace std; // Returns length of LCS for X[0..m-1], Y[0..n-1] int lcs(string X, string Y, int m, int n)  // Driver code int main() {  string S1 = 'AGGTAB';  string S2 = 'GXTXAYB';  int m = S1.size();  int n = S2.size();  cout << 'Length of LCS is ' << lcs(S1, S2, m, n);  return 0; } // This code is contributed by rathbhupendra>

 // A Naive recursive implementation // of LCS problem #include  int max(int a, int b); // Returns length of LCS for X[0..m-1], // Y[0..n-1] int lcs(char* X, char* Y, int i, int j)  // Utility function to get max of // 2 integers int max(int a, int b) { return (a>b) ? a: b; } // Kód ovladače int main() { char S1[] = 'BD';  char S2[] = 'ABCD';  int m = strlen(S1);  int n = strlen(S2);  int i = 0, j = 0;  // Volání funkce printf('Délka LCS je %d', lcs(S1, S2, i, j));  návrat 0; }>

Jáva

 // A Naive recursive implementation of LCS problem in java import java.io.*; import java.util.*; public class LongestCommonSubsequence {  // Returns length of LCS for X[0..m-1], Y[0..n-1]  int lcs(String X, String Y, int m, int n)   n == 0)  return 0;  if (X.charAt(m - 1) == Y.charAt(n - 1))  return 1 + lcs(X, Y, m - 1, n - 1);  else  return max(lcs(X, Y, m, n - 1),  lcs(X, Y, m - 1, n));    // Utility function to get max of 2 integers  int max(int a, int b) { return (a>b) ? a: b; } // Kód ovladače public static void main(String[] args) { LongestCommonSubsequence lcs = new LongestCommonSubsequence();  Řetězec S1 = 'AGGTAB';  Řetězec S2 = 'GXTXAYB';  int m = S1.délka();  int n = S2.délka();  System.out.println('Délka LCS je' + ' ' + lcs.lcs(S1, S2, m, n));  } } // Tento kód přidal Saket Kumar>

Krajta

 # A Naive recursive Python implementation of LCS problem def lcs(X, Y, m, n): if m == 0 or n == 0: return 0 elif X[m-1] == Y[n-1]: return 1 + lcs(X, Y, m-1, n-1) else: return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n)) # Driver code if __name__ == '__main__': S1 = 'AGGTAB' S2 = 'GXTXAYB' print('Length of LCS is', lcs(S1, S2, len(S1), len(S2)))>

 // C# Naive recursive implementation of LCS problem using System; class GFG {  // Returns length of LCS for X[0..m-1], Y[0..n-1]  static int lcs(String X, String Y, int m, int n)    if (m == 0   // Utility function to get max of 2 integers  static int max(int a, int b) { return (a>b) ? a: b; } // Kód ovladače public static void Main() { String S1 = 'AGGTAB';  Řetězec S2 = 'GXTXAYB';  int m = S1.Délka;  int n = S2.Délka;  Console.Write('Délka LCS je' + ' ' + lcs(S1, S2, m, n));  } } // Tento kód je autorem Sam007>

Javascript

PHP

  // A Naive recursive PHP  // implementation of LCS problem  function lcs($X, $Y, $m, $n)  $n == 0) return 0; else if ($X[$m - 1] == $Y[$n - 1]) return 1 + lcs($X, $Y, $m - 1, $n - 1); else return max(lcs($X, $Y, $m, $n - 1), lcs($X, $Y, $m - 1, $n));  // Driver Code  $S1 = 'AGGTAB'; $S2 = 'GXTXAYB'; echo 'Length of LCS is '; echo lcs($S1 , $S2, strlen($S1), strlen($S2)); // This code is contributed  // by Shivi_Aggarwal  ?>>

Výstup

Length of LCS is 4>

Časová náročnost: O(2^m+n)
Pomocný prostor: O(1)

Použití nejdelší společné podsekvence (LCS). Memorizace :

Pokud si pozorně všimneme, můžeme pozorovat, že výše uvedené rekurzivní řešení má následující dvě vlastnosti:

1. Optimální spodní struktura:

Viz pro řešení struktury L(X[0, 1, . . ., m-1], Y[0, 1, . . . , n-1]) používáme podstruktury X[0 , 1, …, m-2], Y[0, 1,…, n-2], v závislosti na situaci (tj. jejich optimálním využití) k nalezení řešení celku.

2. Překrývající se dílčí problémy:

Pokud použijeme výše uvedený rekurzivní přístup pro řetězce BD a abeceda , dostaneme strom částečné rekurze, jak je ukázáno níže. Zde vidíme, že podproblém L(BD, ABCD) se počítá vícekrát. Pokud vezmeme v úvahu celkový strom, bude existovat několik takových překrývajících se dílčích problémů.

L(AXYT, AYZX)
/
L(AXY, AYZX) L(AXYT, AYZ)
/ /
L(AX, AYZX) L(AXY, AYZ) L(AXY, AYZ) L(AXYT, AY)

Přístup: Vzhledem k přítomnosti těchto dvou vlastností můžeme k řešení problému použít dynamické programování nebo zapamatování. Níže je uveden přístup k řešení pomocí rekurze.

Vytvořte rekurzivní funkci. Vytvořte také 2D pole pro uložení výsledku jedinečného stavu.
Pokud je během rekurzivního volání stejný stav volán více než jednou, můžeme přímo vrátit odpověď uloženou pro tento stav namísto opětovného výpočtu.

Níže je uvedena implementace výše uvedeného přístupu:

C++

 // A Top-Down DP implementation // of LCS problem #include  using namespace std; // Returns length of LCS for X[0..m-1], // Y[0..n-1] int lcs(char* X, char* Y, int m, int n,  vector>& dp) { if (m == 0 || n == 0) return 0;  if (X[m - 1] == Y[n - 1]) vrátí dp[m][n] = 1 + lcs(X, Y, m - 1, n - 1, dp);  if (dp[m][n] != -1) { return dp[m][n];  } return dp[m][n] = max(lcs(X, Y, m, n - 1, dp), lcs(X, Y, m - 1, n, dp)); } // Kód ovladače int main() { char X[] = 'AGGTAB';  char Y[] = 'GXTXAYB';  int m = strlen(X);  int n = strlen(Y);  vektor> dp(m + 1, vektor (n + 1, -1));  cout<< 'Length of LCS is ' << lcs(X, Y, m, n, dp);  return 0; }>

Jáva

 /*package whatever //do not write package name here */ import java.io.*; class GFG {  // A Top-Down DP implementation of LCS problem  // Returns length of LCS for X[0..m-1], Y[0..n-1]  static int lcs(String X, String Y, int m, int n,  int[][] dp)  {  if (m == 0 || n == 0)  return 0;  if (dp[m][n] != -1)  return dp[m][n];  if (X.charAt(m - 1) == Y.charAt(n - 1)) {  dp[m][n] = 1 + lcs(X, Y, m - 1, n - 1, dp);  return dp[m][n];  }  dp[m][n] = Math.max(lcs(X, Y, m, n - 1, dp),  lcs(X, Y, m - 1, n, dp));  return dp[m][n];  }  // Drivers code  public static void main(String args[])  {  String X = 'AGGTAB';  String Y = 'GXTXAYB';  int m = X.length();  int n = Y.length();  int[][] dp = new int[m + 1][n + 1];  for (int i = 0; i < m + 1; i++) {  for (int j = 0; j < n + 1; j++) {  dp[i][j] = -1;  }  }  System.out.println('Length of LCS is '  + lcs(X, Y, m, n, dp));  } } // This code is contributed by shinjanpatra>

Krajta

 # A Top-Down DP implementation of LCS problem # Returns length of LCS for X[0..m-1], Y[0..n-1] def lcs(X, Y, m, n, dp): if (m == 0 or n == 0): return 0 if (dp[m][n] != -1): return dp[m][n] if X[m - 1] == Y[n - 1]: dp[m][n] = 1 + lcs(X, Y, m - 1, n - 1, dp) return dp[m][n] dp[m][n] = max(lcs(X, Y, m, n - 1, dp), lcs(X, Y, m - 1, n, dp)) return dp[m][n] # Driver code X = 'AGGTAB' Y = 'GXTXAYB' m = len(X) n = len(Y) dp = [[-1 for i in range(n + 1)]for j in range(m + 1)] print(f'Length of LCS is {lcs(X, Y, m, n, dp)}') # This code is contributed by shinjanpatra>

 /* C# Naive recursive implementation of LCS problem */ using System; class GFG {  /* Returns length of LCS for X[0..m-1], Y[0..n-1] */  static int lcs(char[] X, char[] Y, int m, int n,  int[, ] L)  {  if (m == 0 || n == 0)  return 0;  if (L[m, n] != -1)  return L[m, n];  if (X[m - 1] == Y[n - 1]) {  L[m, n] = 1 + lcs(X, Y, m - 1, n - 1, L);  return L[m, n];  }  L[m, n] = max(lcs(X, Y, m, n - 1, L),  lcs(X, Y, m - 1, n, L));  return L[m, n];  }  /* Utility function to get max of 2 integers */  static int max(int a, int b) { return (a>b) ? a: b; } public static void Main() { String s1 = 'AGGTAB';  Řetězec s2 = 'GXTXAYB';  char[] X = s1.ToCharArray();  char[] Y = s2.ToCharArray();  int m = X.délka;  int n = Y. Délka;  int[, ] L = nový int[m + 1, n + 1];  for (int i = 0; i<= m; i++) {  for (int j = 0; j <= n; j++) {  L[i, j] = -1;  }  }  Console.Write('Length of LCS is'  + ' ' + lcs(X, Y, m, n, L));  } } // This code is contributed by akshitsaxenaa09>

Javascript

 /* A Top-Down DP implementation of LCS problem */ /* Returns length of LCS for X[0..m-1], Y[0..n-1] */ function lcs(X, Y, m, n, dp) {  if (m == 0 || n == 0)  return 0;  if (X[m - 1] == Y[n - 1])  return dp[m][n] = 1 + lcs(X, Y, m - 1, n - 1, dp);  if (dp[m][n] != -1) {  return dp[m][n];  }  return dp[m][n] = Math.max(lcs(X, Y, m, n - 1, dp),  lcs(X, Y, m - 1, n, dp)); } /* Driver code */ let X = 'AGGTAB'; let Y = 'GXTXAYB'; let m = X.length; let n = Y.length; let dp = new Array(m + 1); for(let i = 0; i < m + 1; i++) {  dp[i] = new Array(n + 1).fill(-1); }  console.log('Length of LCS is ' + lcs(X, Y, m, n, dp)); // This code is contributed by shinjanpatra>

Výstup

Length of LCS is 4>

Časová náročnost: O(m * n) kde m a n jsou délky řetězců.
Pomocný prostor: O(m * n) Zde se ignoruje rekurzivní zásobníkový prostor.

Nejdelší společná podsekvence (LCS) pomocí zdola nahoru (tabulka):

K implementaci přístupu dynamického programování pro LCS můžeme použít následující kroky.

Vytvořte 2D pole dp[][] s řádky a sloupci rovnými délce každého vstupního řetězce plus 1 [počet řádků udává indexy S1 a sloupce označují indexy S2 ].
Inicializujte první řádek a sloupec pole dp na 0.
Iterujte řádky pole dp, počínaje 1 (řekněme pomocí iterátoru i ).
- Pro každého i , iterujte všechny sloupce z j = 1 až n :
  - Li S1[i-1] je rovný S2[j-1] , nastavte aktuální prvek pole dp na hodnotu prvku na ( dp[i-1][j-1] + 1 ).
  - Jinak nastavte aktuální prvek pole dp na maximální hodnotu dp[i-1][j] a dp[i][j-1] .
Po vnořených smyčkách bude poslední prvek pole dp obsahovat délku LCS.

Pro lepší pochopení se podívejte na níže uvedený obrázek:

Ilustrace:

Řekněme, že struny jsou S1 = AGGTAB a S2 = GXTXAYB .

První krok: Nejprve vytvořte 2D matici (řekněme dp[][]) o velikosti 8 x 7, jejíž první řádek a první sloupec jsou vyplněny 0.

Vytvoření tabulky dp
Druhý krok: Přechod pro i = 1. Když se j stane 5, S1[0] a S2[4] jsou stejné. Takže dp[][] je aktualizován. Pro ostatní prvky vezměte maximum dp[i-1][j] a dp[i][j-1]. (Pokud jsou v tomto případě obě hodnoty stejné, použili jsme šipky k předchozím řádkům).

Vyplnění řádku č. 1
Třetí krok: Při procházení pro i = 2 jsou S1[1] a S2[0] stejné (oba jsou ‚G‘). Hodnota dp v této buňce se tedy aktualizuje. Zbývající prvky jsou aktualizovány podle podmínek.

Vyplnění řádku č. 2
Čtvrtý krok: Pro i = 3 jsou S1[2] a S2[0] opět stejné. Aktualizace jsou následující.

Vyplnění řádku č. 3
Pátý krok: Pro i = 4 můžeme vidět, že S1[3] a S2[2] jsou stejné. Takže dp[4][3] aktualizováno jako dp[3][2] + 1 = 2.

Vyplnění řady 4
Šestý krok: Zde můžeme vidět, že pro i = 5 a j = 5 jsou hodnoty S1[4] a S2[4] stejné (tj. obě jsou „A“). Takže dp[5][5] se odpovídajícím způsobem aktualizuje a stane se 3.

Vyplnění řady 5
Závěrečný krok: Pro i = 6, viz poslední znaky obou řetězců jsou stejné (jsou to ‚B‘). Proto hodnota dp[6][7] bude 4.

Vyplnění poslední řady
Dostaneme tedy maximální délku společné podsekvence as 4 .

Následuje tabulka implementace pro problém LCS.

C++

 // Dynamic Programming C++ implementation // of LCS problem #include  using namespace std; // Returns length of LCS for X[0..m-1], // Y[0..n-1] int lcs(string X, string Y, int m, int n) {  // Initializing a matrix of size  // (m+1)*(n+1)  int L[m + 1][n + 1];  // Following steps build L[m+1][n+1]  // in bottom up fashion. Note that  // L[i][j] contains length of LCS of  // X[0..i-1] and Y[0..j-1]  for (int i = 0; i <= m; i++) {  for (int j = 0; j <= n; j++)   if (i == 0   }  // L[m][n] contains length of LCS  // for X[0..n-1] and Y[0..m-1]  return L[m][n]; } // Driver code int main() {  string S1 = 'AGGTAB';  string S2 = 'GXTXAYB';  int m = S1.size();  int n = S2.size();  // Function call  cout << 'Length of LCS is ' << lcs(S1, S2, m, n);  return 0; }>

Jáva

 // Dynamic Programming Java implementation of LCS problem import java.util.*; public class LongestCommonSubsequence {  // Returns length of LCS for X[0..m-1], Y[0..n-1]  int lcs(String X, String Y, int m, int n)  {  int L[][] = new int[m + 1][n + 1];  // Following steps build L[m+1][n+1] in bottom up  // fashion. Note that L[i][j] contains length of LCS  // of X[0..i-1] and Y[0..j-1]  for (int i = 0; i <= m; i++) {  for (int j = 0; j <= n; j++)  j == 0)  L[i][j] = 0;  else if (X.charAt(i - 1) == Y.charAt(j - 1))  L[i][j] = L[i - 1][j - 1] + 1;  else  L[i][j] = max(L[i - 1][j], L[i][j - 1]);    }  return L[m][n];  }  // Utility function to get max of 2 integers  int max(int a, int b) { return (a>b) ? a: b; } public static void main(String[] args) { LongestCommonSubsequence lcs = new LongestCommonSubsequence();  Řetězec S1 = 'AGGTAB';  Řetězec S2 = 'GXTXAYB';  int m = S1.délka();  int n = S2.délka();  System.out.println('Délka LCS je' + ' ' + lcs.lcs(S1, S2, m, n));  } } // Tento kód přidal Saket Kumar>

Krajta

 # Dynamic Programming implementation of LCS problem def lcs(X, Y, m, n): # Declaring the array for storing the dp values L = [[None]*(n+1) for i in range(m+1)] # Following steps build L[m+1][n+1] in bottom up fashion # Note: L[i][j] contains length of LCS of X[0..i-1] # and Y[0..j-1] for i in range(m+1): for j in range(n+1): if i == 0 or j == 0: L[i][j] = 0 elif X[i-1] == Y[j-1]: L[i][j] = L[i-1][j-1]+1 else: L[i][j] = max(L[i-1][j], L[i][j-1]) # L[m][n] contains the length of LCS of X[0..n-1] & Y[0..m-1] return L[m][n] # Driver code if __name__ == '__main__': S1 = 'AGGTAB' S2 = 'GXTXAYB' m = len(S1) n = len(S2) print('Length of LCS is', lcs(S1, S2, m, n)) # This code is contributed by Nikhil Kumar Singh(nickzuck_007)>

 // Dynamic Programming implementation of LCS problem using System; class GFG {  // Returns length of LCS for X[0..m-1], Y[0..n-1]  static int lcs(String X, String Y, int m, int n)  {  int[, ] L = new int[m + 1, n + 1];  // Following steps build L[m+1][n+1]  // in bottom up fashion.  // Note that L[i][j] contains length of  // LCS of X[0..i-1] and Y[0..j-1]  for (int i = 0; i <= m; i++) {  for (int j = 0; j <= n; j++)  j == 0)  L[i, j] = 0;  else if (X[i - 1] == Y[j - 1])  L[i, j] = L[i - 1, j - 1] + 1;  else  L[i, j] = max(L[i - 1, j], L[i, j - 1]);    }  return L[m, n];  }  // Utility function to get max of 2 integers  static int max(int a, int b) { return (a>b) ? a: b; } // Kód ovladače public static void Main() { String S1 = 'AGGTAB';  Řetězec S2 = 'GXTXAYB';  int m = S1.Délka;  int n = S2.Délka;  Console.Write('Délka LCS je' + ' ' + lcs(S1, S2, m, n));  } } // Tento kód je autorem Sam007>

Javascript

 // Dynamic Programming Java implementation of LCS problem // Utility function to get max of 2 integers  function max(a, b) {  if (a>b) vrátit a;  jinak vrátit b; } // Vrátí délku LCS pro X[0..m-1], Y[0..n-1] funkci lcs(X, Y, m, n) { var L = new Array(m + 1);  for(var i = 0; i< L.length; i++)   {  L[i] = new Array(n + 1);  }  var i, j;    /* Following steps build L[m+1][n+1] in  bottom up fashion. Note that L[i][j]  contains length of LCS of X[0..i-1]  and Y[0..j-1] */  for(i = 0; i <= m; i++)  {  for(j = 0; j <= n; j++)   j == 0)  L[i][j] = 0;  else if (X[i - 1] == Y[j - 1])  L[i][j] = L[i - 1][j - 1] + 1;  else  L[i][j] = max(L[i - 1][j], L[i][j - 1]);    }    /* L[m][n] contains length of LCS  for X[0..n-1] and Y[0..m-1] */  return L[m][n]; } // Driver code var S1 = 'AGGTAB'; var S2 = 'GXTXAYB'; var m = S1.length; var n = S2.length; console.log('Length of LCS is ' + lcs(S1, S2, m, n)); // This code is contributed by akshitsaxenaa09>

PHP

  // Dynamic Programming C#  // implementation of LCS problem  function lcs($X , $Y, $m, $n) { // Following steps build L[m+1][n+1]  // in bottom up fashion .  // Note: L[i][j] contains length of  // LCS of X[0..i-1] and Y[0..j-1] for ($i = 0; $i <= $m; $i++) { for ($j = 0; $j <= $n; $j++)  if ($i == 0  } // L[m][n] contains the length of  // LCS of X[0..n-1] & Y[0..m-1]  return $L[$m][$n]; } // Driver Code  $S1 = 'AGGTAB'; $S2 = 'GXTXAYB'; $m = strlen($S1); $n = strlen($S2) ; echo 'Length of LCS is '; echo lcs($S1, $S2, $m, $n); // This code is contributed  // by Shivi_Aggarwal  ?>>

Výstup

Length of LCS is 4>

Časová náročnost: O(m * n), což je mnohem lepší než nejhorší případ časové složitosti naivní rekurzivní implementace.
Pomocný prostor: O(m * n), protože algoritmus používá pole velikosti (m+1)*(n+1) k uložení délky společných podřetězců.

Nejdelší společná podsekvence (LCS) pomocí zdola nahoru (optimalizace prostoru):

Ve výše uvedeném tabelačním přístupu používáme L[i-1][j] a L[i][j] atd., zde L[i-1] bude odkazovat na předchozí řádek matice L a L[i] odkazuje na aktuální řádek.
Optimalizaci prostoru můžeme provést pomocí dvou vektorů, jeden je předchozí a druhý je aktuální.
Když vnitřní smyčka for opustí, inicializujeme předchozí rovno aktuální.

Níže je implementace:

rodič jquery

C++

 // Dynamic Programming C++ implementation // of LCS problem #include  using namespace std; int longestCommonSubsequence(string& text1, string& text2) {  int n = text1.size();  int m = text2.size();  // initializing 2 vectors of size m  vector prev(m + 1, 0), cur(m + 1, 0);  for (int idx2 = 0; idx2< m + 1; idx2++)  cur[idx2] = 0;  for (int idx1 = 1; idx1 < n + 1; idx1++) {  for (int idx2 = 1; idx2 < m + 1; idx2++) {  // if matching  if (text1[idx1 - 1] == text2[idx2 - 1])  cur[idx2] = 1 + prev[idx2 - 1];  // not matching  else  cur[idx2]  = 0 + max(cur[idx2 - 1], prev[idx2]);  }  prev = cur;  }  return cur[m]; } int main() {  string S1 = 'AGGTAB';  string S2 = 'GXTXAYB';  // Function call  cout << 'Length of LCS is '  << longestCommonSubsequence(S1, S2);  return 0; }>

Jáva

 // Dynamic Programming Java implementation of LCS problem import java.util.Arrays; public class GFG {  public static int longestCommonSubsequence(String text1, String text2) {  int n = text1.length();  int m = text2.length();  // Initializing 2 arrays of size m  int[] prev = new int[m + 1];  int[] cur = new int[m + 1];  for (int idx1 = 1; idx1 < n + 1; idx1++) {  for (int idx2 = 1; idx2 < m + 1; idx2++) {  // If matching  if (text1.charAt(idx1 - 1) == text2.charAt(idx2 - 1))  cur[idx2] = 1 + prev[idx2 - 1];  // Not matching  else  cur[idx2] = Math.max(cur[idx2 - 1], prev[idx2]);  }  prev = Arrays.copyOf(cur, m + 1);  }  return cur[m];  }  public static void main(String[] args) {  String S1 = 'AGGTAB';  String S2 = 'GXTXAYB';  // Function call  System.out.println('Length of LCS is ' + longestCommonSubsequence(S1, S2));  } }>

Krajta

 def longestCommonSubsequence(text1, text2): n = len(text1) m = len(text2) # Initializing two lists of size m prev = [0] * (m + 1) cur = [0] * (m + 1) for idx1 in range(1, n + 1): for idx2 in range(1, m + 1): # If characters are matching if text1[idx1 - 1] == text2[idx2 - 1]: cur[idx2] = 1 + prev[idx2 - 1] else: # If characters are not matching cur[idx2] = max(cur[idx2 - 1], prev[idx2]) prev = cur.copy() return cur[m] if __name__ == '__main__': S1 = 'AGGTAB' S2 = 'GXTXAYB' # Function call print('Length of LCS is', longestCommonSubsequence(S1, S2)) # This code is contributed by Rishabh Mathur>

 using System; class Program {  static int LongestCommonSubsequence(string text1, string text2)  {  int n = text1.Length;  int m = text2.Length;  // initializing 2 arrays of size m  int[] prev = new int[m + 1];  int[] cur = new int[m + 1];  for (int idx2 = 0; idx2 < m + 1; idx2++)  cur[idx2] = 0;  for (int idx1 = 1; idx1 < n + 1; idx1++)  {  for (int idx2 = 1; idx2 < m + 1; idx2++)  {  // if matching  if (text1[idx1 - 1] == text2[idx2 - 1])  cur[idx2] = 1 + prev[idx2 - 1];  // not matching  else  cur[idx2] = 0 + Math.Max(cur[idx2 - 1], prev[idx2]);  }  prev = cur;  }  return cur[m];  }  static void Main()  {  string S1 = 'AGGTAB';  string S2 = 'GXTXAYB';  // Function call  Console.WriteLine('Length of LCS is ' + LongestCommonSubsequence(S1, S2));  } }>

Javascript

 function longestCommonSubsequence(text1, text2) {  const n = text1.length;  const m = text2.length;  // Initializing two arrays of size m  let prev = new Array(m + 1).fill(0);  let cur = new Array(m + 1).fill(0);  for (let idx2 = 0; idx2 < m + 1; idx2++) {  cur[idx2] = 0;  }  for (let idx1 = 1; idx1 < n + 1; idx1++) {  for (let idx2 = 1; idx2 < m + 1; idx2++) {  // If characters match  if (text1[idx1 - 1] === text2[idx2 - 1]) {  cur[idx2] = 1 + prev[idx2 - 1];  }  // If characters don't match  else {  cur[idx2] = Math.max(cur[idx2 - 1], prev[idx2]);  }  }  // Update the 'prev' array  prev = [...cur];  }  return cur[m]; } // Main function function main() {  const S1 = 'AGGTAB';  const S2 = 'GXTXAYB';  // Function call  console.log('Length of LCS is ' + longestCommonSubsequence(S1, S2)); } // Call the main function main();>

Výstup

Length of LCS is 4>

Časová náročnost: O(m * n), což zůstává stejné.
Pomocný prostor: O(m), protože algoritmus používá dvě pole o velikosti m.