In tất cả các chuỗi con chung dài nhất theo thứ tự từ vựng trong C ++

Trong bài toán này, chúng ta được cung cấp hai chuỗi str1 và str2. Nhiệm vụ của chúng tôi là tạo một chương trình để In tất cả các dãy con chung dài nhất theo thứ tự từ vựng.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào: str1 =“gfare”, str2 =“rfare”

Đầu ra: giá vé

Phương pháp tiếp cận giải pháp

Trong bài toán này, chúng ta sẽ tìm tất cả các dãy con chung dài nhất có thể có và lưu trữ chúng trong ma trận 2D bằng cách sử dụng Lập trình động. Sau đó, chúng tôi sẽ in đầu ra được sắp xếp bằng cách tìm kiếm các ký tự từ a đến z trong LCS.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

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

Đầu ra

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