Chương trình đếm số chuỗi con đồng nhất trong Python

Cho chuỗi s, đếm số chuỗi con đồng nhất (tất cả ký tự giống nhau). Kết quả modulo 10⁹+7.

Ví dụ: s = "xyyzzzxx" → 13 chuỗi con: "x" (3 lần), "xx" (1), "y" (2), "yy" (1), "z" (3), "zz" (2), "zzz" (1). Tổng = 3+1+2+1+3+2+1 = 13.

Giải thuật

1. Thêm ký tự đặc biệt "@" vào cuối s để xử lý khối cuối.
2. Duyệt chuỗi, nhóm các ký tự liên tiếp giống nhau, đếm độ dài mỗi khối.
3. Với mỗi khối độ dài t, số chuỗi con đồng nhất = t*(t+1)/2.
4. Tổng tất cả, lấy modulo 10⁹+7.

Ví dụ minh họa

def solve(s):
    s += "@"
    h = {}
    prev = s[0]
    c = 1
    for ch in s[1:]:
        if prev != ch:
            key = prev * c
            h[key] = h.get(key, 0) + 1
            c = 1
        if prev == ch:
            c += 1
        prev = ch
    fin = 0
    for key in h:
        t = len(key)
        k = t * (t + 1) // 2
        fin += k * h[key]
    return fin % 1000000007

s = "xyyzzzxx"
print(solve(s))

Đầu vào

"xyyzzzxx"

Đầu ra

13