Chương trình tìm số ký tự thêm ít nhất vào cuối chuỗi để thành palindrome trong Python

Cho chuỗi s. Tìm số ký tự tối thiểu cần thêm vào **cuối** chuỗi để thành palindrome.

Ví dụ: "mad" → 2 (thêm "am" → "madam").

Giải thuật (Rolling Hash - Tìm tiền tố palindrome dài nhất kết thúc tại cuối)

1. Chuyển ký tự thành số (0-25). Dùng base b=256, mod m=1e9+7.
2. Duyệt từ phải sang trái, duy trì hash tiến (l) và hash lùi (r) của hậu tố.
3. Khi l == r: hậu tố s[i:] là palindrome → cần thêm i ký tự (nghịch đảo tiền tố s[:i]).
4. Trả về i nhỏ nhất tìm được (duyệt từ phải sang trái nên đầu tiên là lớn nhất).

Ví dụ minh họa

class Solution:
    def solve(self, s):
        b = 256
        m = 10**9 + 7
        arr = [ord(c) - 97 for c in s]
        n = len(arr)
        if n == 0:
            return 0
        l = r = arr[-1]
        res = n - 1
        p = b
        for i in range(n - 2, -1, -1):
            r = (r + arr[i] * p) % m
            l = (l * b + arr[i]) % m
            p = (p * b) % m
            if l == r:
                res = i
        return res

ob = Solution()
s = "mad"
print(ob.solve(s))  # Output: 2

Đầu vào / Đầu ra

Input: "mad"

Output: 2