โปรแกรมหาต้นทุนต่ำสุดในการสร้างสตริงที่กำหนดใน Python

สร้างสตริง str ความยาว n ด้วย 2 Operation:

1. เพิ่มตัวอักษรเดี่ยวท้ายสตริง ค่าใช้จ่าย a
2. เพิ่มซับสตริง sub_str ท้ายสตริง ค่าใช้จ่าย r

หาต้นทุนรวมต่ำสุด

ตัวอย่าง: a=5, r=4, str='tpoint' → 29

t  (+5) → tp (+5) → tpo (+5) → tpoi (+5) → tpoin (+5) → tpoint (+4 substring 't')
Total = 5+5+5+5+5+4 = 29

ขั้นตอน (Dynamic Programming + Z-Algorithm)

1. คำนวณ largest[i] = ความยาวซับสตริงสูงสุดที่สิ้นสุดที่ i และปรากฏก่อนหน้า
2. DP: c[i] = min(c[i-1]+a, c[i-largest[i]]+r)
3. คืน c[-1]

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

def solve(a, r, str):
    size = len(str)
    largest = []
    low = 0
    for upp in range(1, size+1):
        while str[low:upp] not in str[:low]:
            low += 1
        largest.append(upp - low)
    c = [a]
    for i in range(1, size):
        if largest[i] == 0:
            c.append(c[-1] + a)
        else:
            c.append(min(c[-1] + a, c[i - largest[i]] + r))
    return c[-1]

print(solve(5, 4, 'tpoint'))  # Output: 29

อินพุต

5, 4, 'tpoint'

เอาต์พุต

29