Chương trình tìm độ tương đồng giữa chuỗi và các hậu tố của nó trong Python

Cho một chuỗi input_str. Xét tất cả các hậu tố của chuỗi này (ví dụ: 'abcd' có hậu tố 'abc', 'bcd', 'cd', 'd'). Độ tương đồng giữa chuỗi gốc và một hậu tố được định nghĩa là độ dài tiền tố chung dài nhất của chúng. Bài toán yêu cầu tính tổng độ tương đồng giữa chuỗi gốc và tất cả các hậu tố.

Ví dụ, với input_str = 'tpotp', kết quả là 7:

'tpotp' similarity 5
'potp' similarity 0
'otp' similarity 0
'tp' similarity 2
'p' similarity 0
Sum = 5 + 0 + 0 + 2 + 0 = 7

Thuật toán giải quyết (Z-algorithm)

1. Khởi tạo return_list = [len(input_str)] (hậu tố trùng khớp toàn bộ chuỗi)
2. Thiết lập i = 1, p = 0, q = 0, r = 0
3. Khi i < len(input_str):
   • Nếu q < i < q + p (bên trong cửa sổ Z hiện tại):
     • Nếu return_list[i-q] >= q + p - i: thiết lập r = q + p - i, reset p, q = 0
     • Ngược lại: thêm return_list[i-q] vào kết quả, tăng i, reset r = 0
   • Ngược lại (bên ngoài cửa sổ Z): mở rộng thủ công so sánh input_str[r] với input_str[i+r]
   • Thêm r vào return_list, cập nhật p = r, q = i, tăng i, reset r = 0
4. Trả về tổng các phần tử trong return_list

Ví dụ minh họa

def solve(input_str):
    return_list = [len(input_str)]
    i = 1
    p, q = 0, 0
    r = 0
    while i < len(input_str):
        if q < i < (q + p):
            if return_list[i-q] >= q + p - i:
                r = q + p - i
                p, q = 0, 0
            else:
                return_list.append(return_list[i-q])
                i += 1
                r = 0
        else:
            while i + r < len(input_str) and input_str[r] == input_str[i+r]:
                r += 1
            return_list.append(r)
            p, q = r, i
            i += 1
            r = 0
    return sum(return_list)

print(solve('tpotp'))

Đầu vào

'tpotp'

Đầu ra

7