Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> C++

Đếm các dãy con phân biệt trong C++

Cho hai chuỗi S và T. Bài toán yêu cầu đếm số lượng các dãy con phân biệt của S bằng với T.

Chúng ta biết rằng dãy con (subsequence) của một chuỗi là chuỗi mới được hình thành từ chuỗi gốc bằng cách loại bỏ một số ký tự (có thể không loại bỏ nào) mà không làm thay đổi vị trí tương đối của các ký tự còn lại. (Ví dụ: "ACE" là dãy con của "ABCDE" trong khi "AEC" không phải).

Nếu chuỗi đầu vào là "baalllloonnn" và "balloon", sẽ có 36 cách chọn khác nhau.

Giải thuật

Để giải bài toán này, ta thực hiện các bước sau:

  • n := độ dài của s, m := độ dài của t. Cập nhật s và t bằng cách thêm khoảng trắng ở đầu.
  • Tạo ma trận dp kích thước (n + 1) x (m + 1).
  • Khởi tạo dp[0][0] := 1, sau đó đặt giá trị 1 cho toàn bộ cột thứ 0 của mọi hàng.
  • Với i từ 1 đến n:
    • Với j từ 1 đến m:
      • Nếu s[i] = t[j], thì dp[i][j] := dp[i - 1][j - 1]
      • dp[i][j] := dp[i][j] + dp[i - 1][j]
  • Trả về dp[n][m].

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

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;

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

int main() {
    Solution ob;
    cout << (ob.numDistinct("baalllloonnn", "balloon"));
    return 0;
}

Đầu vào

"baalllloonnn" "balloon"

Đầu ra

36