Đếm dãy con chung của hai chuỗi trong C++

Cho hai chuỗi str1, str2. Đếm số dãy con chung (common subsequences) của cả hai chuỗi.

Ví dụ

str1 = "abc", str2 = "ab" → 3 dãy con chung: {'a', 'b', 'ab'}

str1 = "ajblqcpdz", str2 = "aefcnbtdi" → 11 dãy con chung

Phương pháp (Quy hoạch động)

• Tạo mảng dp[n1+1][n2+1] khởi tạo 0.
• Duyệt i=1..n1, j=1..n2:
  • Nếu str1[i-1] == str2[j-1]: dp[i][j] = 1 + dp[i][j-1] + dp[i-1][j].
  • Ngược lại: dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1].
• Trả về dp[n1][n2].

Ví dụ minh họa (C++)

#include <iostream>
using namespace std;

int countsequences(string str, string str2) {
    int n1 = str.length();
    int n2 = str2.length();
    int dp[n1+1][n2+1];
    for (int i = 0; i <= n1; i++)
        for (int j = 0; j <= n2; j++)
            dp[i][j] = 0;
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            if (str[i - 1] == str2[j - 1]) {
                dp[i][j] = 1 + dp[i][j - 1] + dp[i - 1][j];
            } else {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1];
            }
        }
    }
    return dp[n1][n2];
}

int main() {
    string str = "abcdejkil";
    string str2 = "bcdfkaoenlp";
    cout << "count is: " << countsequences(str, str2) << endl;
    return 0;
}

Đầu ra

count is: 51