C++에서 사전순으로 가장 긴 공통 하위 시퀀스를 모두 인쇄합니다.

이 문제에서는 두 개의 문자열 str1과 str2가 제공됩니다. 우리의 임무는 사전순으로 가장 긴 공통 하위 시퀀스를 모두 인쇄하는 프로그램을 만드는 것입니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

입력: str1 ="gfare" , str2 ="rfare"

출력: 요금

솔루션 접근 방식

이 문제에서는 가능한 가장 긴 공통 부분 수열을 모두 찾아 동적 프로그래밍을 사용하여 2D 행렬에 저장합니다. 그런 다음 정렬된 출력을 인쇄합니다. LCS에서 a에서 z까지의 문자를 검색하여.

우리 솔루션의 작동을 설명하는 프로그램,

예시

#include<iostream>
#include<cstring>
#define MAX 100
using namespace std;

int LCSLength = 0;
int DP[MAX][MAX];

int calcLCSLenght(string str1, string str2, int l1, int l2, int i, int j) {
   
   int &lcsLen = DP[i][j];
   if (i==l1 || j==l2)
      return lcsLen = 0;
   if (lcsLen != -1)
      return lcsLen;

   lcsLen = 0;
   
   if (str1[i] == str2[j])
      lcsLen = 1 + calcLCSLenght(str1, str2, l1, l2, i+1, j+1);
   else
      lcsLen = max(calcLCSLenght(str1, str2, l1, l2, i+1, j), calcLCSLenght(str1, str2, l1, l2, i, j+1));
   return lcsLen;
}

void printAllLCS(string str1, string str2, int l1, int l2, char data[], int index1, int index2, int currentLCSlength) {
   if (currentLCSlength == LCSLength) {
     
      data[currentLCSlength] = '\0';
      puts(data);
      return;
   }
   if (index1==l1 || index2==l2)
      return;
   for (char ch='a'; ch<='z'; ch++) {
     
      bool done = false;
      for (int i=index1; i<l1; i++) {
         if (ch==str1[i]) {
            for (int j=index2; j<l2; j++) {
               if (ch==str2[j] && calcLCSLenght(str1, str2, l1, l2, i, j) == LCSLength-currentLCSlength) {
                  data[currentLCSlength] = ch;
                  printAllLCS(str1, str2, l1, l2, data, i+1, j+1, currentLCSlength+1);
                  done = true;
                  break;
               }
            }
         }
         if (done)
            break;
      }
   }
}

int main() {
   
   string str1 = "xysxysx", str2 = "xsyxsyx";
   
   int l1 = str1.length(), l2 = str2.length();
   memset(DP, -1, sizeof(DP));
   LCSLength = calcLCSLenght(str1, str2, l1, l2, 0, 0);
   char data[MAX];
   cout<<"All longest common sub-sequences in lexicographical order are\n";
   printAllLCS(str1, str2, l1, l2, data, 0, 0, 0);
   return 0;
}

출력

All longest common sub-sequences in lexicographical order are
xsxsx
xsxyx
xsysx
xysyx
xyxsx
xyxyx