Một vụ trọng án vừa xảy ra. Tại hiện trường người ta tìm thấy một mẩu giấy nhỏ ghi dòng chữ chứa các kí tự la tinh. Đây là một manh mối quan trọng để phá vụ án này. Đội nghiệp vụ phá án đã phát hiện có một nhóm tội phạm thường mã hóa tin của mình dưới dạng các xâu đối xứng. Để thu hẹp phạm vi tìm kiếm nghi can. Trước hết cần phải kiểm tra dòng chữ trên mẩu giấy, tìm một xâu con đối xứng có độ dài lớn nhất. Nếu trong trường hợp có nhiều xâu con thỏa mãn thì mật mã là xâu con đối xứng có thứ tự từ điển lớn nhất tìm được. (Với xâu con là một dãy các kí tự liên tiếp)
Yêu cầu: Hãy xác định mật mã ghi trong mẩu giấy đó.
Dữ liệu: Vào từ tệp PALIN.INP gồm:
Kết quả: Ghi ra tệp văn bản PALIN.OUT gồm:
Ví dụ:
PALIN.INP |
PALIN.OUT |
4 Abab |
3 bab |
Chú ý: Có 50% số test của bài có n ≤ 100