โปรแกรมหาจำนวนตัวอักษรขั้นต่ำที่ต้องเพิ่มท้ายสตริงให้เป็นพาลินโดรมใน Python

ได้รับสตริง s หา จำนวนตัวอักษรน้อยที่สุดที่ต้องเพิ่มต่อท้าย ให้กลายเป็นพาลินโดรม

ตัวอย่าง

Input: "mad"

Output: 2 (เพิ่ม "am" → "madam")

แนวทางแก้ปัญหา

Rolling Hash (Rabin-Karp) แบบ Two-way:

• คำนวณ hash แบบ forward (l) และ backward (r) พร้อมกัน
• ขยายจากขวาไปซ้าย: ถ้า l == r → substring s[i:] เป็นพาลินโดรม
• คำตอบ = i (จำนวนตัวอักษรก่อนหน้าที่ต้องเพิ่ม)

ใช้ base 256, mod 10^9+7 หลีกเลี่ยง collision

การใช้งาน (Python)

class Solution:
    def solve(self, s):
        b = 256
        mod = 10**9 + 7
        
        # แปลงเป็นตัวเลข 0-25
        arr = [ord(c) - 97 for c in s]
        n = len(arr)
        
        # เริ่มจากตัวสุดท้าย
        l = r = arr[-1]
        p = b
        res = n - 1
        
        for i in range(n - 2, -1, -1):
            # Extend hash
            r = (r + arr[i] * p) % mod
            l = (l * b + arr[i]) % mod
            p = (p * b) % mod
            
            if l == r:
                res = i
        
        return res

# ทดสอบ
ob = Solution()
print(ob.solve("mad"))  # Output: 2

วิธีทางเลือก: KMP / LPS Array (Exact, ไม่มี collision)

def min_chars_to_add(s):
    # หา longest suffix ที่เป็น palindrome
    # ใช้ KMP บน s + '#' + reverse(s)
    rev = s[::-1]
    combined = s + '#' + rev
    lps = [0] * len(combined)
    
    for i in range(1, len(combined)):
        j = lps[i - 1]
        while j > 0 and combined[i] != combined[j]:
            j = lps[j - 1]
        if combined[i] == combined[j]:
            j += 1
        lps[i] = j
    
    # lps[-1] = longest prefix of rev matching suffix of s
    # = longest palindromic suffix
    return len(s) - lps[-1]

ความซับซ้อน

• Rolling Hash: O(N) time, O(1) space (มีโอกาส collision น้อย)
• KMP: O(N) time, O(N) space (Exact)