Chương trình Python đếm substring toàn chữ số 1 trong chuỗi nhị phân

Cho chuỗi nhị phân s. Đếm số substring chỉ chứa ký tự '1'. Kết quả mod 10⁹+7.

Ví dụ

Input: s = "100111"

Output: 7

Các substring: "1" (4 lần), "11" (2 lần), "111" (1 lần).

Thuật toán (Đếm chuỗi 1 liên tiếp)

1. Duyệt chuỗi, biến a đếm độ dài chuỗi '1' liên tiếp hiện tại.
2. Gặp '0' → reset a = 0.
3. Gặp '1' → a += 1, count += a (vì chuỗi dài a thêm a substring mới kết thúc tại vị trí này).

Mã nguồn Python

def solve(s):
    a = 0
    count = 0
    MOD = 10**9 + 7
    for ch in s:
        if ch == '0':
            a = 0
        else:
            a += 1
            count = (count + a) % MOD
    return count

# Test
s = "100111"
print(solve(s))  # Output: 7

Độ phức tạp

• Thời gian: O(n)
• Không gian: O(1)