โปรแกรมหาความคล้ายคลึงระหว่างสตริงกับซัฟฟิกซ์ของมันใน Python

ให้สตริง input_str หาผลรวมของความคล้ายคลึงระหว่างสตริงต้นฉบับกับทุกซัฟฟิกซ์ โดยความคล้ายคลึงวัดจากความยาวของ Longest Common Prefix (LCP)

ตัวอย่าง: input_str = 'tpotp' ผลลัพธ์ = 7

ซัฟฟิกซ์ทั้งหมด: 'tpotp', 'potp', 'otp', 'tp', 'p'

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

ขั้นตอนการแก้ปัญหา (Z-Algorithm แบบปรับเปลี่ยน)

1. สร้าง return_list เริ่มต้นด้วย [len(input_str)]
2. ใช้ตัวแปร i, p, q, r ติดตามช่วงที่ตรงกันล่าสุด
3. วนลูป i จาก 1 ถึง len(input_str)-1:
   • ถ้าอยู่ในช่วงที่รู้จัก (q < i < q+p) ใช้ค่า Z ที่คำนวณไว้
   • มิฉะนั้น เปรียบเทียบตัวอักษรโดยตรงเพื่อหา r
4. คืนค่า sum(return_list)

ตัวอย่างโค้ด

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'))  # Output: 7

อินพุต

'tpotp'

เอาต์พุต

7