โปรแกรมหาความยาว Chunked Palindrome Decomposition สูงสุดใน Python

ปัญหา

กำหนด String text หา k สูงสุด ที่ text = a₁ + a₂ + ... + aₖ โดย aᵢ ≠ "" และ aᵢ = aₖ₊₁₋ᵢ (Palindrome ของ Chunks)

ตัวอย่าง

text = "antaprezatepzapreanta" → Output: 11

Split: "a|nt|a|pre|za|tpe|za|pre|a|nt|a"

อัลกอริทึม (Greedy Two Pointers)

1. Two Pointers: i จากซ้าย, j จากขวา
2. ลองขยาย Chunk จากขอบเขต: เปรียบเทียบ Substring [ic:i] กับ [j:jc]
3. ถ้าเท่ากัน → Found Matching Pair → Counter += 2, Update Boundaries
4. ทำซ้ำจน i > j
5. ถ้าเหลือส่วนกลาง (ic ≠ jc) → Counter += 1 (Center Chunk)

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

def solve(text):
    counter = 0
    i, j = 1, len(text) - 1
    ic, jc = 0, len(text)
    
    while i <= j:
        if text[ic:i] == text[j:jc]:
            counter += 2
            ic = i
            jc = j
        i += 1
        j -= 1
    
    if ic != jc:
        counter += 1
    return counter

text = "antaprezatepzapreanta"
print(solve(text))  # 11

ความซับซ้อน

• Time: O(n²) Worst Case (String Comparison แต่ละรอบ)
• Space: O(1)
• Optimization: ใช้ Rolling Hash (Rabin-Karp) ลดเป็น O(n)