Chương trình Python tìm substring tại vị trí cho trước trong tập hợp tất cả substring của nhiều chuỗi

Cho n chuỗi str₁..strₙ. substr_i = tập tất cả substring của str_i. substr_union = union của tất cả substr_i, sắp xếp lexicographically. Cho q truy vấn, mỗi truy vấn hỏi phần tử thứ k (1-indexed) trong substr_union.

Ví dụ: strings = ['pqr', 'pqt'], queries = [4, 7, 9] → ['pqt', 'qt', 't'].

Thuật toánSuffix Array / LCP

• Thu thập tất cả suffix của mọi chuỗi, loại trùng lặp.
• Sắp xếp suffix.
• Tính LCP (Longest Common Prefix) giữa các suffix liền kề.
• Mỗi suffix đóng góp len(suffix) - LCP substring mới.
• Duyệt qua các suffix theo thứ tự, trừ dần k để tìm substring thứ k.

Ví dụ mã nguồn

def lng_i(suff, lng, i):
    d = zip(suff, lng)
    lo = hi = 0
    for suf, lng_val in d:
        if lng_val is None:
            lng_val = 0
        hi += len(suf) - lng_val
        if hi - 1 == i:
            return suf
        elif hi - 1 > i:
            for p, q in enumerate(range(lng_val, len(suf))):
                if lo + p == i:
                    return suf[:q+1]
        lo = hi
    return False

def hlp_ii(str1, str2):
    ub = min(len(str1), len(str2))
    cnt = 0
    for i in range(ub):
        if str1[i] == str2[i]:
            cnt += 1
        else:
            return cnt
    return cnt

def solve(strings, q_list):
    t_dict = {}
    suff = []
    lng = []
    for st in strings:
        for i in range(len(st)):
            value = st[i:]
            if value not in t_dict:
                t_dict[value] = 1
                suff.append(value)
    suff.sort()
    for i in range(len(suff)):
        if i == 0:
            lng.append(None)
        else:
            lng.append(hlp_ii(suff[i-1], suff[i]))
    res = []
    for q in q_list:
        res.append(lng_i(suff, lng, q-1))
    return res

print(solve(['pqr', 'pqt'], [4, 7, 9]))  # ['pqt', 'qt', 't']

Đầu vào / Đầu ra

Input:  ['pqr', 'pqt'], [4, 7, 9]
Output: ['pqt', 'qt', 't']