Bài toán yêu cầu tính số lần chuỗi t xuất hiện như một dãy con của chuỗi s.

Ví dụ:

Nhập: s = "rabbbit", t = "rabbit"
Output: 3
Giải thích:
Có 3 cách để tạo thành "rabbit" từ "rabbbit".

Và một ví dụ khác:

Nhập: s = "babgbag", t = "bag"
Output: 5
Giải thích:
Có 5 cách để tạo thành "bag" từ "babgbag".

Dưới đây là giải pháp sử dụng lập trình động (Dynamic Programming).

Tư duy giải quyết vấn đề

Chúng ta sẽ so sánh từng ký tự giữa hai chuỗi s và t. Nếu các ký tự khớp, chúng ta có thể chọn sử dụng hoặc không sử dụng ký tự đó. Nếu không khớp, chúng ta buộc phải bỏ qua ký tự trong chuỗi s.

Ký hiệu mảng DP

dp[i][j]: Số lượng cách mà chuỗi con của s[0..i-1] có thể tạo thành chuỗi t[0..j-1].

Công thức chuyển tiếp

• Nếu s[i - 1] == t[j - 1], thì:
  • Sử dụng ký tự hiện tại: dp[i - 1][j - 1].
  • Không sử dụng ký tự hiện tại: dp[i - 1][j].
  • Vậy dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j].
• Nếu s[i - 1] != t[j - 1], thì:
  • Chỉ có thể bỏ qua ký tự hiện tại của s: dp[i][j] = dp[i - 1][j].

Khoi tao mang DP

• dp[i][0] = 1: Dãy rỗng luôn là dãy con của bất kỳ chuỗi nào.
• dp[0][j] = 0: Không thể tạo ra chuỗi không rỗng từ dãy rỗng.

Thuật toán bằng C++

#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    int countSubsequences(string source, string target) {
        int lenS = source.size();
        int lenT = target.size();

        // Khởi tạo ma trận DP
        vector<vector<unsigned long long>> dp(lenS + 1, vector<unsigned long long>(lenT + 1, 0));

        // Khoi tao hang dau cua DP
        for(int i = 0; i <= lenS; ++i){
            dp[i][0] = 1;
        }

        // Duyet qua cac ky tu cua chuoi nguon va muc tieu
        for(int i = 1; i <= lenS; ++i){
            for(int j = 1; j <= lenT; ++j){
                if(source[i - 1] == target[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else{
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[lenS][lenT];
    }
};

int main(){
    string source, target;

    cout << "Source string: ";
    getline(cin, source);

    cout << "Target string: ";
    getline(cin, target);

    Solution solver;
    int result = solver.countSubsequences(source, target);

    cout << "Result: " << result << endl;
    
    return 0;
}