Thi thử Duyên hải 2021 - Lần 2 - Bài 2 - Khoá then chốt
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Để mã hóa một khóa ~s~ không rỗng, đầu tiên điệp viên chọn một chuỗi ~t~ sao cho chuỗi ~s~ là một chuỗi tiền tố của ~t~, và chuỗi nghịch đảo của ~s~ là hậu tố của chuỗi ~t~. Trong trường hợp này, chuỗi ~t~ có thể ghi các ký hiệu không liên quan đến chuỗi ~s~. Sau đó, một số ngẫu nhiên ~m~ (có thể ~m = 0)~ ký tự ngẫu nhiên được đưa vào bên trái của ~t~, mà ~m~ ký tự ngẫu nhiên được thêm vào bên phải ~t~. Bây giờ, chuỗi ~t~ là mã hóa của ~s~.
Rõ ràng với ~t~, có thể có nhiều ~s~. Do đó, người ta quyết định rằng khóa ~s~ phải là chuỗi dài nhất trong tất cả các tùy chọn có thể, và trong trường hợp có nhiều tùy chọn dài nhất, chọn số lượng các ký tự ngẫu nhiên thêm vào bên trái và vào bên phải là tối thiểu, nghĩa là, chuỗi ~t~ có chiều dài tối đa. Bạn cần phải thực hiện thuật toán phục hồi khoá ~s~ từ phiên bản được mã hóa ~t~.
Input
Dòng đầu tiên ghi số nguyên ~n~ - số khóa mà bạn cần phải giải mã.
Mỗi dòng trong ~n~ dòng sau là một chuỗi mã hóa ~t~, chỉ gồm chữ cái thường trong bảng chữ cái Latinh. Tổng chiều dài của tất cả các khóa không vượt quá 100.000 ký tự. Đảm bảo rằng mỗi phiên bản mật mã có ít nhất một khoá không rỗng.
Output
Với mỗi bản mã ~t~, in ra trên một dòng khóa ~s~ tương ứng.
Sample Input
3
ababc
ababa
cxbaydzabxe
Sample Output
bab
ababa
xba
Bình luận
Em xin đóng góp lời giải bài này như sau ạ