Chương trình tìm số chuỗi con khác nhau cho nhiều truy vấn trong Python

Cho chuỗi độ dài và danh sách truy vấn (mỗi truy vấn ). Với mỗi truy vấn, đếm số chuỗi con khác nhau của .

Ví dụ: , → kết quả .

Thuật toán giải quyết (Suffix Array + LCP - Kasai Algorithm)

1. Với mỗi truy vấn:
   • Trích xuất chuỗi con
   • Xây dựng Suffix Array của (sắp xếp các hậu tố)
   • Tính mảng LCP (Longest Common Prefix) giữa các hậu tố liền kề bằng thuật toán Kasai
   • Số chuỗi con khác nhau = tổng độ dài hậu tố - tổng LCP

Ví dụ minh họa

def kasai(s, suff, n):
    lcp = [0] * n
    inv = [0] * n
    for i in range(n):
        inv[suff[i]] = i
    k = 0
    for i in range(n):
        if inv[i] == n-1:
            k = 0
            continue
        j = suff[inv[i] + 1]
        while i + k < n and j + k < n and s[i+k] == s[j+k]:
            k += 1
        lcp[inv[i]] = k
        if k > 0:
            k -= 1
    return lcp

def solve(s, Q):
    res = []
    for i in range(len(Q)):
        left, right = Q[i]
        sub = s[left:right+1]
        length = right - left + 1
        suffix = [[i, sub[i:]] for i in range(length)]
        suffix.sort(key=lambda x: x[1])
        suff, suffix = [list(t) for t in zip(*suffix)]
        lcp = kasai(sub, suff, length)
        count = len(suffix[0])
        for i in range(length-1):
            count += len(suffix[i+1]) - lcp[i]
        res.append(count)
    return res

s = "pptpp"
Q = [(1,1),(1,4),(1,1),(0,2)]
print(solve(s, Q))

Đầu vào

"pptpp", [(1,1),(1,4),(1,1),(0,2)]

Đầu ra

[1, 8, 1, 5]