C++에서 다른 문자열의 하위 문자열인 한 문자열의 가장 긴 하위 시퀀스의 길이 찾기

두 개의 문자열 X와 Y가 있고 시퀀스 Y의 하위 문자열인 문자열 X의 가장 긴 하위 시퀀스의 길이를 찾아야 한다고 가정합니다. 따라서 X ="ABCD"이고 Y ="BACDBDCD"이면 출력은 3이 됩니다. . "ACD"는 Y의 부분 문자열인 X의 가장 긴 부분 시퀀스이기 때문입니다.

여기서 우리는 이 문제를 해결하기 위해 동적 프로그래밍 접근 방식을 사용할 것입니다. 따라서 X의 길이가 n이고 Y의 길이가 m이면 (m+1)x(n+1) 차수의 DP 배열을 만듭니다. DP[i, j]의 값은 Y[0…i]의 부분 문자열인 X[0…j]의 부분 시퀀스의 최대 길이입니다. 이제 DP의 각 셀에 대해 다음과 같이 됩니다.

• 1~m 범위의 i:
  • 1 ~ n
    범위의 j에 대해
    • X[i – 1]이 Y[j – i]와 같으면 DP[i, j] :=1 + DP[i – 1, j – 1]
    • 그렇지 않으면 DP[i, j] :=1 + DP[i, j – 1]

그리고 마지막으로 y의 부분 문자열인 x의 가장 긴 부분 시퀀스의 길이는 max(DP[i, n])입니다. 여기서 1 <=i <=m.

예시

#include<iostream>
#define MAX 100
using namespace std;
int maxSubLength(string x, string y) {
   int table[MAX][MAX];
   int n = x.length();
   int m = y.length();
   for (int i = 0; i <= m; i++)
      for (int j = 0; j <= n; j++)
   table[i][j] = 0;
   for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= n; j++) {
         if (x[j - 1] == y[i - 1])
            table[i][j] = 1 + table[i - 1][j - 1];
         else
            table[i][j] = table[i][j - 1];
      }
   }
   int ans = 0;
   for (int i = 1; i <= m; i++)
   ans = max(ans, table[i][n]);
   return ans;
}
int main() {
   string x = "ABCD";
   string y = "BACDBDCD";
   cout << "Length of Maximum subsequence substring is: " << maxSubLength(x, y);
}

출력

Length of Maximum subsequence substring is: 3