Chương trình tìm độ dài dãy con chung dài nhất trong C++

Cho hai chuỗi text1 và text2, hãy tìm độ dài của dãy con chung dài nhất (Longest Common Subsequence - LCS). Dãy con của một chuỗi là chuỗi mới được tạo ra bằng cách xóa một số ký tự mà không thay đổi thứ tự tương đối của các ký tự còn lại. (Ví dụ: "abe" là dãy con của "abcde" nhưng "adc" không phải). Dãy con chung của hai chuỗi là dãy con xuất hiện trong cả hai. Nếu không có dãy con chung, trả về 0. Ví dụ: "abcde" và "ace" cho kết quả 3.

Thuật toán

• Gán n = text1.size(), m = text2.size(). Nếu n == 0 hoặc m == 0, trả về 0.
• Thêm một ký tự khoảng trắng ở đầu mỗi chuỗi để chỉ số bắt đầu từ 1.
• Khởi tạo ma trận dp kích thước (n+1) x (m+1) với giá trị 0.
• Duyệt i từ 1 đến n, j từ 1 đến m:
  • dp[i][j] = max(dp[i][j-1], dp[i-1][j]).
  • Nếu text1[i] == text2[j]: dp[i][j] = max(dp[i][j], 1 + dp[i-1][j-1]).
• Trả về dp[n][m].

Ví dụ triển khai (C++)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int longestCommonSubsequence(string s, string x) {
        int n = s.size();
        int m = x.size();
        if (!n || !m) return 0;
        s = " " + s;
        x = " " + x;
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
                if (s[i] == x[j]) {
                    dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
                }
            }
        }
        return dp[n][m];
    }
};

int main() {
    Solution ob;
    cout << ob.longestCommonSubsequence("abcde", "ace");
    return 0;
}

Đầu vào

"abcde" "ace"

Đầu ra

3