Med tanke på två strängar, S1 och S2 , uppgiften är att hitta längden på den längsta gemensamma undersekvensen, dvs den längsta undersekvensen som finns i båda strängarna.

A längsta vanliga följdsekvensen (LCS) definieras som den längsta delsekvensen som är vanlig i alla givna ingångssekvenser.

Längsta vanliga efterföljd

Exempel:

Inmatning: S1 = ABC, S2 = ACD
Produktion: 2
Förklaring: Den längsta undersekvensen som finns i båda strängarna är AC.

Inmatning: S1 = AGGTAB, S2 = GXTXAYB
Produktion: 4
Förklaring: Den längsta vanliga undersekvensen är GTAB.

Inmatning: S1 = ABC, S2 = CBA
Produktion: 1
Förklaring: Det finns tre vanliga undersekvenser av längden 1, A, B och C och ingen gemensam undersekvens med längden mer än 1.

Inmatning: S1 = XYZW, S2 = XYWZ
Produktion: 3
Förklaring: Det finns två vanliga delsekvenser med längden 3 XYZ och XYW, och ingen gemensam delsekvens. längd mer än 3.

Longest Common Subsequence (LCS) med hjälp av rekursion:

Generera alla möjliga undersekvenser och hitta den längsta bland dem som finns i båda strängarna med hjälp av Följ stegen nedan för att implementera idén:

• Skapa en rekursiv funktion [säg lcs() ].
• Kontrollera förhållandet mellan de första tecknen i strängarna som ännu inte är bearbetade.
  • Beroende på relationen anropar nästa rekursiva funktion som nämnts ovan.
• Returnera längden på det mottagna LCS som svar.

Nedan följer implementeringen av det rekursiva tillvägagångssättet:

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>

C

// 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; } // Drivrutinskod int main() { char S1[] = 'BD';  char S2[] = 'ABCD';  int m = strlen(Sl);  int n = strlen(S2);  int i = 0, j = 0;  // Funktionsanrop printf('Längden på LCS är %d', lcs(S1, S2, i, j));  returnera 0; }>

Java

// 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; } // Driver code public static void main(String[] args) { LongestCommonSubsequence lcs = new LongestCommonSubsequence();  Sträng S1 = 'AGGTAB';  Sträng S2 = 'GXTXAYB';  int m = S1.length();  int n = S2.length();  System.out.println('Längden på LCS är' + ' ' + lcs.lcs(S1, S2, m, n));  } } // Denna kod är bidragit av Saket Kumar>

Pytonorm

# 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#

// 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; } // Driver code public static void Main() { String S1 = 'AGGTAB';  Sträng S2 = 'GXTXAYB';  int m = S1.Längd;  int n = S2.Längd;  Console.Write('Längden på LCS är' + ' ' + lcs(S1, S2, m, n));  } } // Denna kod är bidragit från 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  ?>>

Produktion

Length of LCS is 4>

Tidskomplexitet: O(2^m+n)
Hjälputrymme: O(1)

Longest Common Subsequence (LCS) med hjälp av Memoisering :

Om vi ​​lägger märke till det noggrant kan vi observera att ovanstående rekursiva lösning har följande två egenskaper:

1. Optimal understruktur:

Se för att lösa strukturen för L(X[0, 1, . . ., m-1], Y[0, 1, . . . , n-1]) vi tar hjälp av understrukturerna av X[0 , 1, …, m-2], Y[0, 1,…, n-2], beroende på situationen (dvs använda dem optimalt) för att hitta lösningen av helheten.

2. Överlappande delproblem:

Om vi ​​använder ovanstående rekursiva tillvägagångssätt för strängar BD och ABCD , kommer vi att få ett partiellt rekursionsträd som visas nedan. Här kan vi se att delproblemet L(BD, ABCD) beräknas mer än en gång. Om det totala trädet beaktas kommer det att finnas flera sådana överlappande delproblem.

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

Närma sig: På grund av närvaron av dessa två egenskaper kan vi använda dynamisk programmering eller memoisering för att lösa problemet. Nedan är tillvägagångssättet för lösningen med hjälp av rekursion.

• Skapa en rekursiv funktion. Skapa också en 2D-array för att lagra resultatet av ett unikt tillstånd.
• Under rekursionsanropet, om samma tillstånd anropas mer än en gång, kan vi direkt returnera svaret som lagrats för det tillståndet istället för att beräkna igen.

Nedan är implementeringen av ovanstående tillvägagångssätt:

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) returnera 0;  om (X[m - 1] == Y[n - 1]) returnera dp[m][n] = 1 + lcs(X, Y, m - 1, n - 1, dp);  if (dp[m][n] != -1) { returnera dp[m][n];  } return dp[m][n] = max(lcs(X, Y, m, n - 1, dp), lcs(X, Y, m - 1, n, dp)); } // Drivrutinskod 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; }>

Java

/*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>

Pytonorm

# 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#

/* 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';  Sträng s2 = 'GXTXAYB';  char[] X = s1.ToCharArray();  char[] Y = s2.ToCharArray();  int m = X. Längd;  int n = Y. Längd;  int[,] L = ny int[m + 1, n + 1];  för (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>

Produktion

Length of LCS is 4>

Tidskomplexitet: O(m * n) där m och n är stränglängderna.
Hjälputrymme: O(m * n) Här ignoreras det rekursiva stackutrymmet.

govinda skådespelare

Longest Common Subsequence (LCS) med Bottom-Up (Tabulering):

Vi kan använda följande steg för att implementera den dynamiska programmeringsmetoden för LCS.

• Skapa en 2D-array dp[][] med rader och kolumner lika med längden på varje inmatningssträng plus 1 [antalet rader anger indexen för S1 och kolumnerna anger indexen för S2 ].
• Initiera den första raden och kolumnen i dp-matrisen till 0.
• Iterera genom raderna i dp-matrisen, med början från 1 (säg att använda iterator i ).
  • För varje i , iterera alla kolumner från j = 1 till n :
    • Om S1[i-1] är lika med S2[j-1] , ställ in det aktuella elementet i dp-matrisen till elementets värde till ( dp[i-1][j-1] + 1 ).
    • Annars, ställ in det aktuella elementet i dp-matrisen till det maximala värdet av dp[i-1][j] och dp[i][j-1] .
• Efter de kapslade looparna kommer det sista elementet i dp-matrisen att innehålla längden på LCS.

Se illustrationen nedan för en bättre förståelse:

Illustration:

Säg att strängarna är S1 = AGGTAB och S2 = GXTXAYB .

Första steget: Skapa först en 2D-matris (säg dp[][]) med storleken 8 x 7 vars första rad och första kolumn är fyllda med 0.

Skapar dp-tabellen

Andra steg: Traverse för i = 1. När j blir 5 är S1[0] och S2[4] lika. Så dp[][] uppdateras. För de andra elementen ta maxvärdet av dp[i-1][j] och dp[i][j-1]. (I det här fallet, om båda värdena är lika, har vi använt pilar till föregående rader).

Fyller rad nr 1

Tredje steget: Medan genomkörd för i = 2, är S1[1] och S2[0] desamma (båda är 'G'). Så dp-värdet i den cellen uppdateras. Resten av elementen uppdateras enligt villkoren.

Fyller rad nr. 2

Fjärde steget: För i = 3 är S1[2] och S2[0] återigen samma. Uppdateringarna är som följer.

Fyllnadsrad nr. 3

Femte steget: För i = 4 kan vi se att S1[3] och S2[2] är samma. Så dp[4][3] uppdaterades som dp[3][2] + 1 = 2.

Fyllning rad 4

Sjätte steget: Här kan vi se att för i = 5 och j = 5 är värdena för S1[4] och S2[4] desamma (dvs båda är 'A'). Så dp[5][5] uppdateras därefter och blir 3.

Fyllning rad 5

Sista steget: För i = 6, se de sista tecknen i båda strängarna är samma (de är 'B'). Därför blir värdet på dp[6][7] 4.

Fyller den sista raden

Så vi får den maximala längden av gemensam underföljd som 4 .

log4j

Följande är en tabellerad implementering för LCS-problemet.

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

Java

// 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();  Sträng S1 = 'AGGTAB';  Sträng S2 = 'GXTXAYB';  int m = S1.length();  int n = S2.length();  System.out.println('Längden på LCS är' + ' ' + lcs.lcs(S1, S2, m, n));  } } // Denna kod är bidragit av Saket Kumar>

Pytonorm

# 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)>

C#

// 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; } // Driver code public static void Main() { String S1 = 'AGGTAB';  Sträng S2 = 'GXTXAYB';  int m = S1.Längd;  int n = S2.Längd;  Console.Write('Längden på LCS är' + ' ' + lcs(S1, S2, m, n));  } } // Den här koden är bidragit från Sam007>

Javascript

// Dynamic Programming Java implementation of LCS problem // Utility function to get max of 2 integers  function max(a, b) {  if (a>b) returnera a;  annars returnera b; } // Returnerar längden på LCS för X[0..m-1], Y[0..n-1] funktion lcs(X, Y, m, n) { var L = new Array(m + 1);  för(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  ?>>

Produktion

Length of LCS is 4>

Tidskomplexitet: O(m * n) vilket är mycket bättre än det värsta tänkbara tidskomplexiteten för naiv rekursiv implementering.
Hjälputrymme: O(m * n) eftersom algoritmen använder en matris med storlek (m+1)*(n+1) för att lagra längden på de gemensamma delsträngarna.

Längsta Common Subsequence (LCS) med Bottom-Up (Space-Optimization):

• I ovanstående tabuleringsmetod använder vi L[i-1][j] och L[i][j] etc, här refererar L[i-1]-viljan till matrisen L:s föregående rad och L[i] refererar till den aktuella raden.
• Vi kan göra rymdoptimering genom att använda två vektorer en är tidigare och en annan är aktuell.
• När den inre slingan går ut initierar vi föregående lika med ström.

Nedan är implementeringen:

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 föregående (m + 1, 0), cur (m + 1, 0);  för (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; }>

Java

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

Pytonorm

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>

C#

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();>

Produktion

Length of LCS is 4>

Tidskomplexitet: O(m * n), vilket förblir detsamma.
Hjälputrymme: O(m) eftersom algoritmen använder två arrayer med storleken m.