Gitt to strenger, S1 og S2 , er oppgaven å finne lengden på den lengste felles sekvensen, dvs. den lengste sekvensen som er tilstede i begge strengene.

gjennomstrekning

EN lengste vanlige undersekvens (LCS) er definert som den lengste undersekvensen som er vanlig i alle gitte inngangssekvenser.

Lengste vanlige etterfølge

Eksempler:

Inndata: S1 = ABC, S2 = ACD
Produksjon: 2
Forklaring: Den lengste undersekvensen som er tilstede i begge strengene er AC.

Inndata: S1 = AGGTAB, S2 = GXTXAYB
Produksjon: 4
Forklaring: Den lengste vanlige undersekvensen er GTAB.

Inndata: S1 = ABC, S2 = CBA
Produksjon: 1
Forklaring: Det er tre vanlige undersekvenser av lengde 1, A, B og C og ingen felles undersekvens med lengde mer enn 1.

Inndata: S1 = XYZW, S2 = XYWZ
Produksjon: 3
Forklaring: Det er to vanlige undersekvenser med lengde 3 XYZ og XYW, og ingen felles undersekvens. av lengde mer enn 3.

Lengste vanlige undersekvens (LCS) ved bruk av rekursjon:

Generer alle mulige undersekvenser og finn den lengste blant dem som finnes i begge strengene ved hjelp av Følg trinnene nedenfor for å implementere ideen:

python-program for binært søk

• Lag en rekursiv funksjon [si lcs() ].
• Sjekk forholdet mellom de første tegnene i strengene som ennå ikke er behandlet.
  • Avhengig av relasjonen kaller den neste rekursive funksjonen som nevnt ovenfor.
• Returner lengden på LCS mottatt som svar.

Nedenfor er implementeringen av den rekursive tilnærmingen:

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; } // Driverkode int main() { char S1[] = 'BD';  char S2[] = 'ABCD';  int m = strlen(S1);  int n = strlen(S2);  int i = 0, j = 0;  // Funksjonsanrop printf('Lengden på LCS er %d', lcs(S1, S2, i, j));  returner 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();  String S1 = 'AGGTAB';  String S2 = 'GXTXAYB';  int m = S1.length();  int n = S2.length();  System.out.println('Lengden på LCS er' + ' ' + lcs.lcs(S1, S2, m, n));  } } // Denne koden er bidratt av Saket Kumar>

Python

# 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; } // Driverkode offentlig statisk void Main() { String S1 = 'AGGTAB';  String S2 = 'GXTXAYB';  int m = S1. Lengde;  int n = S2. Lengde;  Console.Write('Lengde på LCS er' + ' ' + lcs(S1, S2, m, n));  } } // Denne koden er bidratt av 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  ?>>

Produksjon

Length of LCS is 4>

Tidskompleksitet: O(2^m+n)
Hjelpeplass: O(1)

Lengste vanlige delsekvens (LCS) ved hjelp av Memoisering :

Hvis vi legger merke til det, kan vi observere at den ovennevnte rekursive løsningen har følgende to egenskaper:

1. Optimal understruktur:

Se for å løse strukturen til L(X[0, 1, . . ., m-1], Y[0, 1, . . . , n-1]) vi tar hjelp av understrukturene til X[0 , 1, …, m-2], Y[0, 1,…, n-2], avhengig av situasjonen (dvs. å bruke dem optimalt) for å finne løsningen av helheten.

2. Overlappende underproblemer:

Hvis vi bruker den ovennevnte rekursive tilnærmingen for strenger BD og ABCD , vil vi få et delvis rekursjonstre som vist nedenfor. Her kan vi se at delproblemet L(BD, ABCD) blir beregnet mer enn én gang. Hvis det totale treet vurderes, vil det være flere slike overlappende delproblemer.

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

Nærme seg: På grunn av tilstedeværelsen av disse to egenskapene kan vi bruke Dynamisk programmering eller Memoization for å løse problemet. Nedenfor er tilnærmingen for løsningen ved bruk av rekursjon.

• Lag en rekursiv funksjon. Lag også en 2D-array for å lagre resultatet av en unik tilstand.
• Under rekursjonsanropet, hvis den samme tilstanden kalles mer enn én gang, kan vi direkte returnere svaret som er lagret for den tilstanden i stedet for å beregne på nytt.

Nedenfor er implementeringen av tilnærmingen ovenfor:

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) returner 0;  hvis (X[m - 1] == Y[n - 1]) returner dp[m][n] = 1 + lcs(X, Y, m - 1, n - 1, dp);  if (dp[m][n] != -1) { returner dp[m][n];  } return dp[m][n] = maks(lcs(X, Y, m, n - 1, dp), lcs(X, Y, m - 1, n, dp)); } // Driverkode 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>

Python

# 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';  String s2 = 'GXTXAYB';  char[] X = s1.ToCharArray();  char[] Y = s2.ToCharArray();  int m = X. Lengde;  int n = Y. Lengde;  int[, ] L = ny 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>

Produksjon

Length of LCS is 4>

Tidskompleksitet: O(m * n) hvor m og n er strenglengdene.
Hjelpeplass: O(m * n) Her ignoreres det rekursive stabelrommet.

Lengste vanlige delsekvens (LCS) ved bruk av nedenfra og opp (tabell):

Vi kan bruke følgende trinn for å implementere den dynamiske programmeringstilnærmingen for LCS.

string sammenligne java

• Lag en 2D-array dp[][] med rader og kolonner lik lengden på hver inndatastreng pluss 1 [antall rader indikerer indeksene til S1 og kolonnene indikerer indeksene til S2 ].
• Initialiser den første raden og kolonnen i dp-matrisen til 0.
• Iterer gjennom radene i dp-matrisen, start fra 1 (si bruk iterator Jeg ).
  • For hver Jeg , iterer alle kolonnene fra j = 1 til n :
    • Hvis S1[i-1] er lik S2[j-1] , sett gjeldende element i dp-matrisen til verdien av elementet til ( dp[i-1][j-1] + 1 ).
    • Ellers setter du det gjeldende elementet i dp-matrisen til maksimalverdien av dp[i-1][j] og dp[i][j-1] .
• Etter de nestede løkkene vil det siste elementet i dp-matrisen inneholde lengden på LCS.

Se illustrasjonen nedenfor for en bedre forståelse:

Illustrasjon:

Si at strengene er S1 = AGGTAB og S2 = GXTXAYB .

Første skritt: Opprett først en 2D-matrise (si dp[][]) med størrelse 8 x 7 hvis første rad og første kolonne er fylt med 0.

Oppretter dp-tabellen

Andre trinn: Travers for i = 1. Når j blir 5, er S1[0] og S2[4] like. Så dp[][] er oppdatert. For de andre elementene ta maksimum av dp[i-1][j] og dp[i][j-1]. (I dette tilfellet, hvis begge verdiene er like, har vi brukt piler til de forrige radene).

Fyller rad nr. 1

lytteport

Tredje trinn: Mens krysset for i = 2, er S1[1] og S2[0] de samme (begge er 'G'). Så dp-verdien i den cellen er oppdatert. Resten av elementene oppdateres i henhold til betingelsene.

Fyller radnr. 2

Fjerde trinn: For i = 3 er S1[2] og S2[0] igjen like. Oppdateringene er som følger.

Fyllingsrekke nr. 3

Femte trinn: For i = 4 kan vi se at S1[3] og S2[2] er like. Så dp[4][3] oppdatert som dp[3][2] + 1 = 2.

Fylle rad 4

Sjette trinn: Her kan vi se at for i = 5 og j = 5 er verdiene til S1[4] og S2[4] de samme (dvs. begge er 'A'). Så dp[5][5] oppdateres tilsvarende og blir 3.

Fylle rad 5

Siste trinn: For i = 6, se at de siste tegnene i begge strengene er like (de er 'B'). Derfor blir verdien av dp[6][7] 4.

Fyller den siste raden

Så vi får den maksimale lengden på felles undersekvens som 4 .

java sammenligningsmetode

Følgende er en tabulert implementering for 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();  String S1 = 'AGGTAB';  String S2 = 'GXTXAYB';  int m = S1.length();  int n = S2.length();  System.out.println('Lengden på LCS er' + ' ' + lcs.lcs(S1, S2, m, n));  } } // Denne koden er bidratt av Saket Kumar>

Python

# 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; } // Driverkode offentlig statisk void Main() { String S1 = 'AGGTAB';  String S2 = 'GXTXAYB';  int m = S1. Lengde;  int n = S2. Lengde;  Console.Write('Lengde på LCS er' + ' ' + lcs(S1, S2, m, n));  } } // Denne koden er bidratt av Sam007>

Javascript

// Dynamic Programming Java implementation of LCS problem // Utility function to get max of 2 integers  function max(a, b) {  if (a>b) returnere a;  annet retur b; } // Returnerer lengden på LCS for X[0..m-1], Y[0..n-1] funksjon 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  ?>>

Produksjon

Length of LCS is 4>

Tidskompleksitet: O(m * n) som er mye bedre enn den verste tidskompleksiteten til naiv rekursiv implementering.
Hjelpeplass: O(m * n) fordi algoritmen bruker en matrise med størrelse (m+1)*(n+1) for å lagre lengden på de vanlige delstrengene.

Lengste felles undersekvens (LCS) ved bruk av Bottom-Up (Space-Optimization):

• I tabellen ovenfor bruker vi L[i-1][j] og L[i][j] osv., her refererer L[i-1]-viljen til matrisen Ls forrige rad og L[i] refererer til gjeldende rad.
• Vi kan gjøre plassoptimalisering ved å bruke to vektorer en er tidligere og en annen er gjeldende.
• Når den indre for loop går ut initialiserer vi forrige lik strøm.

Nedenfor er 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 forrige(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; }>

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

Python

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

Produksjon

Length of LCS is 4>

Tidskompleksitet: O(m * n), som forblir den samme.
Hjelpeplass: O(m) fordi algoritmen bruker to matriser med størrelse m.