หาความยาว subsequence ยาวที่สุดของสตริง X ที่เป็น substring ของสตริง Y (C++)

ให้สตริง X และ Y ต้องการหาความยาวของ Subsequence ยาวที่สุดของ X ที่เป็น Substring ของ Y

ตัวอย่าง: X = "ABCD", Y = "BACDBDCD" → ผลลัพธ์คือ 3 เพราะ "ACD" เป็น Subsequence ของ X และเป็น Substring ของ Y

วิธีแก้ด้วย Dynamic Programming

สร้างตาราง DP ขนาด (m+1) × (n+1) โดย m = ความยาว Y, n = ความยาว X

DP[i][j] = ความยาวสูงสุดของ Subsequence ของ X[0..j-1] ที่เป็น Substring ของ Y[0..i-1]

สมการทำซ้ำ:

• ถ้า X[j-1] == Y[i-1]: DP[i][j] = 1 + DP[i-1][j-1]
• อื่นๆ: DP[i][j] = DP[i][j-1]

คำตอบ = 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);
    return 0;
}

ผลลัพธ์

Length of Maximum subsequence substring is: 3

ความซับซ้อน

เวลา: O(m × n), พื้นที่: O(m × n)