Bài 28.5. Cân Bằng Chuỗi Con Đối Xứng Dài Nhất - [Độ khó: Khó]

Trong một dự án xử lý ngôn ngữ tự nhiên, bạn được yêu cầu tìm một "cụm từ đối xứng" có độ dài lớn nhất trong một đoạn văn bản cho trước. Một cụm từ được coi là đối xứng nếu nó đọc xuôi và đọc ngược giống nhau (ví dụ: "madam", "level", "radar"). Nhiệm vụ của bạn là viết một chương trình tìm chuỗi con đối xứng dài nhất trong một chuỗi ký tự đã cho.

INPUT FORMAT

Một dòng duy nhất chứa chuỗi S. Chuỗi S có thể chứa các chữ cái tiếng Anh (a-z, A-Z) và chữ số (0-9). Độ dài của S không quá 2000 ký tự.

OUTPUT FORMAT

Một dòng duy nhất chứa chuỗi con đối xứng dài nhất tìm được. Nếu có nhiều chuỗi con đối xứng dài nhất với cùng độ dài, in ra chuỗi con xuất hiện đầu tiên.

Ví dụ 1:

Input:

babad

Output:

bab

Giải thích:

• Các chuỗi con đối xứng của "babad" là: "b", "a", "d", "bab", "aba".
• Các chuỗi con "bab" và "aba" đều có độ dài 3.
• "bab" xuất hiện đầu tiên trong chuỗi (tại vị trí 0).

Ví dụ 2:

Input:

cbbd

Output:

bb

Giải thích:

• Các chuỗi con đối xứng của "cbbd" là: "c", "b", "d", "bb".
• "bb" là chuỗi con đối xứng dài nhất với độ dài 2.

Ví dụ 3:

Input:

a

Output:

a

Giải thích:

• Với chuỗi chỉ có một ký tự, ký tự đó chính là chuỗi con đối xứng dài nhất.