Chương trình tìm độ dài xâu con palindrome dài nhất bằng Python

Cho chuỗi S (độ dài ≤ 1000). Tìm độ dài xâu con palindrome dài nhất.

Ví dụ: "BABAC" → 3 (xâu con "BAB").

Quy trình giải quyết (Dynamic Programming)

1. Tạo ma trận DP n x n khởi tạo False.
2. Đặt đường chéo chính DP[i][i] = True.
3. Duyệt độ dài l từ 2 đến n:
   • Với mỗi i, tính end = i + l.
   • Nếu l == 2 và S[i] == S[end-1]: DP[i][end-1] = True.
   • Nếu l > 2 và S[i] == S[end-1] và DP[i+1][end-2]: DP[i][end-1] = True.
   • Khi đặt True, cập nhật max_length = l, start = i.
4. Trả về max_length.

Ví dụ mã nguồn

class Solution:
    def solve(self, s):
        dp = [[False for i in range(len(s))] for i in range(len(s))]
        for i in range(len(s)):
            dp[i][i] = True
        max_length = 1
        start = 0
        for l in range(2, len(s) + 1):
            for i in range(len(s) - l + 1):
                end = i + l
                if l == 2:
                    if s[i] == s[end - 1]:
                        dp[i][end - 1] = True
                        max_length = l
                        start = i
                else:
                    if s[i] == s[end - 1] and dp[i + 1][end - 2]:
                        dp[i][end - 1] = True
                        max_length = l
                        start = i
        return max_length

ob = Solution()
print(ob.solve('BABAC'))  # Output: 3

Đầu vào

"ABBABBC"

Đầu ra

5