C++에서 가장 긴 공통 부분 수열

<시간/>

두 개의 문자열 text1과 text2가 있다고 가정하고 가장 긴 공통 부분 시퀀스의 길이를 반환해야 합니다. 문자열의 하위 시퀀스는 나머지 문자의 상대적 순서를 변경하지 않고 일부 문자가 삭제된 원래 문자열에서 생성된 새 문자열입니다. (예를 들어 "abe"는 "abcde"의 하위 시퀀스이지만 "adc"는 그렇지 않습니다). 두 문자열의 공통 하위 시퀀스는 두 문자열에 공통적인 하위 시퀀스입니다. 따라서 공통 부분 수열이 없으면 0을 반환합니다. 입력이 "abcde" 및 "ace"와 같으면 결과는 3이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=s의 크기, m :=x의 크기
n이 0이거나 m이 0이면 0을 반환합니다.
s :=s로 연결된 빈 문자열
x :=x로 연결된 빈 문자열
ret :=0
차수의 행렬 dp 정의 (n + 1) x (m + 1)
범위 1에서 n까지의 i에 대해
- 범위 1에서 m까지의 j에 대해
  - dp[i, j] :=dp[i, j - 1] 및 dp[i – 1, j]
    의 최대값
  - s[i] =x[j]이면
    - dp[i, j] :=dp[i, j]의 최대값, 1 + dp[i – 1, j – 1]
반환 dp[n, m]

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int longestCommonSubsequence(string s, string x) {
      int n = s.size();
      int m = x.size();
      if(!n || !m) return 0;
      s = " " + s;
      x = " " + x;
      int ret = 0;
      vector < vector <int> > dp(n + 1, vector <int>(m + 1));
      for(int i = 1; i <= n; i++){
         for(int j = 1; j <= m ; j++){
            dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            if(s[i] == x[j]) {
               dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
            }
         }
      }
      return dp[n][m];
   }
};
main(){
   Solution ob;
   cout << (ob.longestCommonSubsequence("abcde", "ace"));
}

입력

"abcde"
"ace"

C++에서 가장 긴 공통 부분 수열

예시

입력

출력