두 개의 문자열이 주어지면, S1 그리고 S2 , 작업은 가장 긴 공통 부분 수열의 길이, 즉 두 문자열 모두에 존재하는 가장 긴 부분 수열을 찾는 것입니다.

ㅏ 가장 긴 공통 부분 수열(LCS) 주어진 모든 입력 시퀀스에 공통되는 가장 긴 부분 시퀀스로 정의됩니다.

가장 긴 공통 부분 수열

예:

입력: S1 = ABC, S2 = ACD
산출: 2
설명: 두 문자열 모두에 존재하는 가장 긴 부분 수열은 AC입니다.

입력: S1 = AGGTAB, S2 = GXTXAYB
산출: 4
설명: 가장 긴 공통 부분 수열은 GTAB입니다.

입력: S1 = ABC, S2 = CBA
산출: 1
설명: 길이가 1인 세 개의 공통 부분 수열(A, B, C)이 있고 길이가 1보다 큰 공통 부분 수열은 없습니다.

입력: S1 = XYZW, S2 = XYWZ
산출: 삼
설명: 길이가 3인 XYZ, XYW의 두 개의 공통 부분 수열이 있지만 공통 부분 수열은 없습니다. 길이가 3 이상입니다.

재귀를 사용하는 LCS(최장 공통 부분 수열):

가능한 모든 하위 시퀀스를 생성하고 다음을 사용하여 두 문자열에 모두 존재하는 하위 시퀀스 중에서 가장 긴 것을 찾습니다. 아이디어를 구현하려면 아래 단계를 따르십시오.

자바의 반환 유형

• 재귀 함수를 만듭니다. lcs() ].
• 아직 처리되지 않은 문자열의 첫 번째 문자 간의 관계를 확인합니다.
  • 위에서 언급한 대로 관계에 따라 다음 재귀 함수를 호출합니다.
• 답변으로 받은 LCS의 길이를 반환합니다.

다음은 재귀 접근 방식의 구현입니다.

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>비) ? a : b; } // 드라이버 코드 int main() { char S1[] = 'BD';  char S2[] = 'ABCD';  int m = strlen(S1);  int n = strlen(S2);  int i = 0, j = 0;  // 함수 호출 printf('LCS의 길이는 %d입니다', lcs(S1, S2, i, j));  0을 반환합니다. }>

자바

// 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>비) ? a : b; } // 드라이버 코드 public static void main(String[] args) { LongestCommonSubsequence lcs = new LongestCommonSubsequence();  문자열 S1 = 'AGGTAB';  문자열 S2 = 'GXTXAYB';  int m = S1.length();  int n = S2.length();  System.out.println('LCS의 길이는' + ' ' + lcs.lcs(S1, S2, m, n));  } } // 이 코드는 Saket Kumar가 제공한 것입니다.>

파이썬

# 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>비) ? a : b; } // 드라이버 코드 public static void Main() { String S1 = 'AGGTAB';  문자열 S2 = 'GXTXAYB';  int m = S1.길이;  int n = S2.길이;  Console.Write('LCS의 길이는' + ' ' + lcs(S1, S2, m, n));  } } // 이 코드는 Sam007이 제공한 것입니다.>

자바스크립트

>

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

산출

Length of LCS is 4>

시간 복잡도: 오(2^m+n)
보조 공간: 오(1)

LCS(최장 공통 부분 수열) 사용 메모 :

주의 깊게 살펴보면 위의 재귀 솔루션이 다음 두 가지 속성을 보유하고 있음을 알 수 있습니다.

1. 최적의 하부 구조:

L(X[0, 1, . . ., m-1], Y[0, 1, . . . , n-1])의 구조를 풀려면 X[0의 하위 구조의 도움을 받습니다. , 1, …, m-2], Y[0, 1,…, n-2], 상황에 따라(즉, 최적으로 사용) 전체의 해를 찾는다.

2. 중복되는 하위 문제:

문자열에 대해 위의 재귀적 접근 방식을 사용하면 BD 그리고 ABCD , 우리는 아래와 같이 부분 재귀 트리를 얻을 것입니다. 여기서는 하위 문제 L(BD, ABCD)가 두 번 이상 계산되는 것을 볼 수 있습니다. 전체 트리를 고려하면 겹치는 하위 문제가 여러 개 있을 것입니다.

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

접근하다: 이 두 가지 속성이 있기 때문에 동적 프로그래밍이나 메모화를 사용하여 문제를 해결할 수 있습니다. 다음은 재귀를 사용한 솔루션에 대한 접근 방식입니다.

• 재귀 함수를 만듭니다. 또한 고유한 상태의 결과를 저장하기 위해 2D 배열을 만듭니다.
• 재귀 호출 중에 동일한 상태가 두 번 이상 호출되면 다시 계산하는 대신 해당 상태에 대해 저장된 답변을 직접 반환할 수 있습니다.

다음은 위의 접근 방식을 구현한 것입니다.

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]) 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] = max(lcs(X, Y, m, n - 1, dp), lcs(X, Y, m - 1, n, dp)); } // 드라이버 코드 int main() { char X[] = 'AGGTAB';  char Y[] = 'GXTXAYB';  int m = strlen(X);  int n = strlen(Y);  벡터> dp(m + 1, 벡터 (n + 1, -1));  시합<< 'Length of LCS is ' << lcs(X, Y, m, n, dp);  return 0; }>

자바

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

파이썬

# 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>비) ? a : b; } 공개 정적 무효 Main() { 문자열 s1 = 'AGGTAB';  문자열 s2 = 'GXTXAYB';  char[] X = s1.ToCharArray();  char[] Y = s2.ToCharArray();  int m = X.길이;  int n = Y.길이;  int[, ] L = new 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>

자바스크립트

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

산출

Length of LCS is 4>

시간 복잡도: O(m * n) 여기서 m과 n은 문자열 길이입니다.
보조 공간: O(m * n) 여기서 재귀 스택 공간은 무시됩니다.

상향식을 사용한 가장 긴 공통 부분 수열(LCS)(표 작성):

다음 단계를 사용하여 LCS에 대한 동적 프로그래밍 접근 방식을 구현할 수 있습니다.

• 2D 배열 만들기 dp[][] 행과 열은 각 입력 문자열의 길이에 1을 더한 것과 같습니다. [행의 수는 문자열의 인덱스를 나타냅니다. S1 열은 다음의 인덱스를 나타냅니다. S2 ].
• dp 배열의 첫 번째 행과 열을 0으로 초기화합니다.
• 1부터 시작하여 dp 배열의 행을 반복합니다(예: 반복자를 사용). 나 ).
  • 각각 나 , 다음의 모든 열을 반복합니다. j = 1 ~ n :
    • 만약에 S1[i-1] 동일하다 S2[j-1] , dp 배열의 현재 요소를 요소의 값으로 설정합니다( dp[i-1][j-1] + 1 ).
    • 그렇지 않으면 dp 배열의 현재 요소를 최대값으로 설정합니다. dp[i-1][j] 그리고 dp[i][j-1] .
• 중첩 루프 다음에는 dp 배열의 마지막 요소에 LCS의 길이가 포함됩니다.

더 나은 이해를 위해 아래 그림을 참조하십시오.

삽화:

문자열은 다음과 같습니다. S1 = AGGTAB 그리고 S2 = GXTXAYB .

첫 번째 단계: 처음에 첫 번째 행과 첫 번째 열이 0으로 채워지는 8 x 7 크기의 2D 행렬(예: dp[][])을 만듭니다.

DP 테이블 생성

두번째 단계: i = 1에 대한 트래버스. j가 5가 되면 S1[0]과 S2[4]는 동일합니다. 따라서 dp[][]가 업데이트됩니다. 다른 요소의 경우 최대 dp[i-1][j] 및 dp[i][j-1]을 사용합니다. (이 경우 두 값이 동일하면 이전 행에 화살표를 사용했습니다).

행 번호 1 채우기

세 번째 단계: i = 2로 이동하는 동안 S1[1]과 S2[0]은 동일합니다(둘 다 'G'). 따라서 해당 셀의 dp 값이 업데이트됩니다. 나머지 요소는 조건에 따라 업데이트됩니다.

행 번호 채우기 2

캣 팀프 무게

네 번째 단계: i = 3인 경우 S1[2]와 S2[0]은 다시 동일합니다. 업데이트 내용은 다음과 같습니다.

행 번호 채우기 삼

다섯 번째 단계: i = 4인 경우 S1[3]과 S2[2]가 동일하다는 것을 알 수 있습니다. 따라서 dp[4][3]는 dp[3][2] + 1 = 2로 업데이트되었습니다.

행 4 채우기

여섯 번째 단계: 여기서 i = 5 및 j = 5인 경우 S1[4]와 S2[4]의 값이 동일하다는 것을 알 수 있습니다(즉, 둘 다 'A'). 따라서 dp[5][5]는 이에 따라 업데이트되어 3이 됩니다.

5행 채우기

마지막 단계: i = 6인 경우 두 문자열의 마지막 문자가 동일합니다('B'). 따라서 dp[6][7]의 값은 4가 됩니다.

마지막 행 채우기

따라서 우리는 공통 부분 수열의 최대 길이를 다음과 같이 얻습니다. 4 .

다음은 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; }>

자바

// 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>비) ? a : b; } 공개 정적 void main(String[] args) { LongestCommonSubsequence lcs = new LongestCommonSubsequence();  문자열 S1 = 'AGGTAB';  문자열 S2 = 'GXTXAYB';  int m = S1.length();  int n = S2.length();  System.out.println('LCS의 길이는' + ' ' + lcs.lcs(S1, S2, m, n));  } } // 이 코드는 Saket Kumar가 제공한 것입니다.>

파이썬

# 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>비) ? a : b; } // 드라이버 코드 public static void Main() { String S1 = 'AGGTAB';  문자열 S2 = 'GXTXAYB';  int m = S1.길이;  int n = S2.길이;  Console.Write('LCS의 길이는' + ' ' + lcs(S1, S2, m, n));  } } // 이 코드는 Sam007이 제공한 것입니다.>

자바스크립트

// Dynamic Programming Java implementation of LCS problem // Utility function to get max of 2 integers  function max(a, b) {  if (a>b) a를 반환합니다.  그렇지 않으면 b를 반환합니다. } // X[0..m-1], Y[0..n-1]에 대한 LCS의 길이를 반환합니다. function lcs(X, Y, m, n) { var L = new Array(m + 1);  for(var i = 0; 나는< 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  ?>>

산출

Length of LCS is 4>

시간 복잡도: O(m * n) 이는 Naive Recursive 구현의 최악의 시간 복잡도보다 훨씬 낫습니다.
보조 공간: O(m * n) 이는 알고리즘이 공통 부분 문자열의 길이를 저장하기 위해 (m+1)*(n+1) 크기의 배열을 사용하기 때문입니다.

상향식(공간 최적화)을 사용한 가장 긴 공통 부분 수열(LCS):

• 위의 표 접근 방식에서는 L[i-1][j] 및 L[i][j] 등을 사용합니다. 여기서 L[i-1]은 행렬 L의 이전 행을 참조하고 L[i]는 다음을 참조합니다. 현재 행.
• 하나는 이전 벡터이고 다른 하나는 현재 벡터인 두 벡터를 사용하여 공간 최적화를 수행할 수 있습니다.
• 내부 for 루프가 종료되면 현재와 동일한 이전을 초기화합니다.

구현은 다음과 같습니다.

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), 현재(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; }>

자바

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

파이썬

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

자바스크립트

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

산출

Length of LCS is 4>

시간 복잡도: O(m * n), 이는 동일하게 유지됩니다.
보조 공간: O(m)은 알고리즘이 크기가 m인 두 개의 배열을 사용하기 때문입니다.