พิมพ์ Longest Common Subsequences ทั้งหมดเรียง Lexicographical ใน C++

บทนำ

โจทย์: หา Longest Common Subsequence (LCS) ทุกแบบที่เป็นไปได้ของสตริงสองตัว แล้วพิมพ์เรียง Lexicographical Order

ตัวอย่าง

str1 = "xysxysx", str2 = "xsyxsyx" LCS ทั้งหมด: xsxsx, xsxyx, xsysx, xysyx, xyxsx, xyxyx

แนวทางแก้ปัญหา

1. DP หาความยาว LCS (DP[i][j] = LCS length ของ suffix i, j)
2. Backtracking แบบ Lexicographical: ลองตัวอักษร 'a' ถึง 'z'
3. หาตำแหน่ง i ใน str1 และ j ใน str2 ที่มีตัวอักษรนั้น และ DP[i][j] == remaining length
4. Recursive สร้างสตริงต่อ

ตัวอย่างโค้ด

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

สรุป

DP + Lexicographical Backtracking พิมพ์ LCS ทั้งหมดเรียงสวย ไม่ซ้ำ ใช้ได้กับสตริงความยาวปานกลาง