Chương trình tính tổng độ tương đồng chuỗi với các hậu tố trong Python

Mô tả bài toán

Cho một chuỗi s. Hãy tìm tổng độ tương đồng của s với từng hậu tố của nó. Độ tương đồng giữa hai chuỗi là độ dài tiền tố chung dài nhất.

Ví dụ

Nếu đầu vào là s = "pqpqpp", thì đầu ra sẽ là 11 vì các hậu tố là "pqpqpp", "qpqpp", "pqpp", "qpp", "pp", "p". Độ tương đồng lần lượt là 6, 0, 3, 0, 1, 1. Tổng = 6 + 0 + 3 + 0 + 1 + 1 = 11.

Giải thuật (Z-Algorithm)

1. Khởi tạo length = len(s), total = length, mảng z = [0], l = 0, r = 0.
2. Duyệt k từ 1 đến length - 1:
   • Nếu k > r: đặt match = 0, index = k, so sánh ký tự để mở rộng match.
   • Thêm match vào z.
   • Nếu match > 0: cập nhật total, l = k, r = index - 1.
   • Ngược lại: sử dụng giá trị đã tính trong z để tránh so sánh lại.
3. Trả về total.

Triển khai Python

def solve(s):
    length = len(s)
    total = length
    z = [0]
    l = 0
    r = 0
    for k in range(1, length):
        if k > r:
            match = 0
            index = k
            while index < length:
                if s[index] == s[match]:
                    match += 1
                    index += 1
                else:
                    break
            z.append(match)
            if match > 0:
                total += match
                l = k
                r = index - 1
        else:
            if z[k - l] < (r - k) + 1:
                z.append(z[k - l])
                total += z[k - l]
            else:
                match = r - k
                index = r
                while index < length:
                    if s[index] == s[match]:
                        match += 1
                        index += 1
                    else:
                        break
                z.append(match)
                total += match
                l = k
                r = index - 1
    return total

s = "pqpqpp"
print(solve(s))

Đầu vào

"pqpqpp"

Đầu ra

11