Hoa Tiết Đối Xứng Áo Dài

Mô tả

Bà nội bạn là một thợ may áo dài lão làng ở làng nghề Việt Nam. Mỗi tấm vải lụa trước khi cắt may, bà lại thêu những họa tiết trang trí lên. Đặc biệt, bà rất chuộng họa tiết đối xứng — những đoạn hoa văn đọc từ trái sang hay từ phải sang đều y hệt nhau, giống như hoa sen ở giữa với hai bên lá sen lặp lại đối xứng.

Để tiện quản lý, bà mã hóa dải họa tiết trên vải thành một chuỗi ký tự (chỉ chứa chữ cái in thường). Bạn hãy viết chương trình giúp bà nội tìm ra đoạn họa tiết đối xứng (liên tiếp) dài nhất trên tấm vải đó.

Nếu có nhiều đoạn họa tiết đối xứng cùng đạt độ dài lớn nhất, hãy chọn đoạn xuất hiện sớm nhất (gần mép trái của tấm vải nhất).

Đầu vào

• Một chuỗi s (chỉ gồm các chữ cái in thường 'a' đến 'z').

Đầu ra

• Trả về một chuỗi là đoạn họa tiết đối xứng liên tiếp dài nhất. Nếu có nhiều đáp án cùng độ dài, trả về đoạn gần đầu chuỗi nhất.

Ràng buộc

• Độ dài chuỗi n thỏa mãn 1 <= n <= 1000.

Ví dụ

Ví dụ 1:

• Đầu vào: "abaxyx"
• Đầu ra: "aba"
• Giải thích: Các chuỗi con đối xứng gồm "a", "b", "aba", "x", "y", "xyx". Đoạn "aba" có độ dài 3, lớn nhất. Đáp án là "aba".

Ví dụ 2:

• Đầu vào: "bb"
• Đầu ra: "bb"
• Giải thích: Cả chuỗi "bb" đã đối xứng (tâm là khoảng giữa hai ký tự). Không có đoạn nào dài hơn, nên kết quả là "bb".