Chương trình tìm số dãy con khác nhau trong Python

Mô tả bài toán

Cho chuỗi s. Đếm số dãy con khác nhau (subsequences). Kết quả modulo 10^9 + 7.

Ví dụ

s = "bab" -> 6 (dãy con: "a", "b", "ba", "ab", "bb", "abb").

Giải thuật

1. dp[i]: số dãy con khác nhau kết thúc tại vị trí i.
2. Nếu ký tự s[i] chưa xuất hiện trước đó: dp[i] = 1 + sum(dp[0..i-1]).
3. Nếu đã xuất hiện tại ind: dp[i] = sum(dp[ind..i-1]).
4. Kết quả = sum(dp) % MOD.

Triển khai Python

def solve(s):
    dp, m = [0] * len(s), 10**9 + 7
    for i, char in enumerate(s):
        ind = s.rfind(char, 0, i)
        dp[i] = (1 + sum(dp[:i]) % m) if ind == -1 else (sum(dp[ind:i]) % m)
    return sum(dp) % m

s = "bab"
print(solve(s))

Đầu vào

"bab"

Đầu ra

6