Chương trình tìm độ dài chuỗi con đối xứng dài nhất sau một phép xoay trong Python

Cho một chuỗi s, chúng ta có thể xoay chuỗi tại một vị trí bất kỳ đúng một lần. Tìm độ dài chuỗi con đối xứng (palindrome) dài nhất có thể đạt được sau phép xoay đó.

Ví dụ: s = "elklev" → xoay giữa "el" và "klev" được "levelk", chuỗi con đối xứng dài nhất là "level" (độ dài 5). Kết quả: 5.

Giải thuật (Brute-force trên chuỗi gấp đôi)

Vì xoay chuỗi tương đương với lấy một chuỗi con của s + s có độ dài ≤ len(s).

• Tạo s2 = s + s.
• Khởi tạo max_len = 0.
• Duyệt mọi vị trí bắt đầu x từ 0 đến len(s)-1 và độ dài y từ 0 đến len(s):
  • Lấy chuỗi con temp = s2[x : x + y].
  • Nếu temp là palindrome và len(temp) > max_len, cập nhật max_len.
• Trả về max_len.

Lưu ý: Giải pháp này có độ phức tạp O(n³), phù hợp cho chuỗi ngắn. Đối với chuỗi dài, cần dùng Manacher hoặc các thuật toán tối ưu hơn.

Mã nguồn Python

class Solution:
    def solve(self, s):
        s2 = 2 * s
        max_len = 0
        for x in range(len(s)):
            for y in range(len(s) + 1):
                temp = s2[x : x + y]
                if temp == temp[::-1] and len(temp) > max_len:
                    max_len = len(temp)
        return max_len

ob = Solution()
s = "elklev"
print(ob.solve(s))  # Output: 5

Đầu vào

"elklev"

Đầu ra

5