Chương trình đếm số chuỗi con tương tự cho mỗi truy vấn trong Python

Cho chuỗi và tập truy vấn (mỗi ). Với mỗi chuỗi con , đếm số chuỗi con "tương tự" nó. Hai chuỗi tương tự nếu:

• Cùng độ dài
• Với mọi cặp chỉ số : (cấu trúc bằng nhau)

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

Thuật toán giải quyết (Fingerprint + So sánh cấu trúc)

1. Tính "fingerprint" cho chuỗi: gán số thứ tự cho ký tự lần đầu xuất hiện (VD: "abcab" → "01201")
2. Tiền tính fingerprint cho mọi cửa sổ độ dài 10
3. Với mỗi truy vấn:
   • Lấy fingerprint của chuỗi truy vấn
   • Duyệt mọi vị trí có thể trong :
     • Bỏ qua nhanh nếu fingerprint cửa sổ 10 khác nhau
     • Kiểm tra chi tiết ánh xạ ký tự giữa hai chuỗi con
   • Đếm số khớp

Ví dụ minh họa

fp = []

def calc_fingerprint(s):
    dict = {s[0]: 0}
    fp = "0"
    j = 1
    for i in range(1, len(s)):
        if s[i] not in dict:
            dict[s[i]], j = j, j+1
        fp += str(dict[s[i]])
    return int(fp)

def solve(s, Q):
    if len(s) > 10:
        for i in range(0, len(s)-10):
            fp.append(calc_fingerprint(s[i:i+10]))
    ret = []
    for i in range(len(Q)):
        a, b = Q[i]
        s1 = s[a-1:b]
        k = 0
        for i in range(len(s)-(b-a)):
            if b-a > 9 and fp[a-1] != fp[i]:
                continue
            dict = {}
            s2 = s[i:i+(b-a)+1]
            for i in range(b-a+1):
                if s2[i] not in dict:
                    if s1[i] in dict.values():
                        break
                    dict[s2[i]] = s1[i]
                if dict[s2[i]] != s1[i]:
                    break
            else:
                k += 1
        ret.append(k)
    return ret

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

Đầu vào

"hjhhbcbk", [(1,2), (2,4)]

Đầu ra

[6, 1]