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

สมมติว่ามีสตริง s ต้องการหาผลรวมของความคล้ายคลึง (similarity) ระหว่าง s กับซัฟฟิกซ์ (suffix) ทุกตัวของมันเอง ความคล้ายคลึงระหว่างสองสตริงคือความยาวของคำนำหน้า (prefix) ที่ยาวที่สุดที่เหมือนกัน

ตัวอย่าง: s = "pqpqpp" ผลลัพธ์คือ 11 เพราะซัฟฟิกซ์คือ "pqpqpp", "qpqpp", "pqpp", "qpp", "pp", "p" ความคล้ายคลึงคือ 6,0,3,0,1,1 ผลรวม = 11

วิธีแก้ปัญหา (อัลกอริทึม Z-Algorithm)

1. length := len(s), total := length, z := [0], l := 0, r := 0
2. วน k จาก 1 ถึง length - 1:
   • ถ้า k > r: ตั้ง match := 0, index := k แล้วขยายจับคู่
   • บันทึก match ลง z
   • ถ้า match > 0: อัปเดต total, l, r
   • มิฉะนั้น ใช้ค่า z[k-l] เพื่อข้ามการคำนวณซ้ำ
3. คืนค่า total

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

def solve(s):
    length = len(s)
    total = length
    z = [0]
    l = 0
    r = 0
    for k in range(1, length):
        if k > r:
            match = 0
            index = k
            while index < length:
                if s[index] == s[match]:
                    match += 1
                    index += 1
                else:
                    break
        z.append(match)
        if match > 0:
            total += match
            l = k
            r = index - 1
        else:
            if z[k - l] < (r - k) + 1:
                z.append(z[k - l])
                total += z[k - l]
            else:
                match = r - k
                index = r
                while index < length:
                    if s[index] == s[match]:
                        match += 1
                        index += 1
                    else:
                        break
                z.append(match)
                total += match
                l = k
                r = index - 1
    return total

s = "pqpqpp"
print(solve(s))

อินพุต

"pqpqpp"

เอาต์พุต

11