#1316. SSEQSTRS - Chọn tên

Bộ nhớ: 256 MiB Thời gian: 500 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

NGUỒN: Bài tập thầy Vũ Mạnh Hà - Ôn Hải Phòng 08/11/2020

Trong chuyến thăm Sapa ngắm tuyết, Bờm và Cuội phát hiện ra một loại nấm mới. Hai người quyết định đặt tên cho loại nấm mới này trước khi công bố rộng rãi với thế giới. Bờm chọn tên là xâu kí tự 𝑆 , còn Cuội lại thích tên là xâu kí tự 𝑇 . Với tinh thần khoa học, hai bạn thống nhất sẽ dùng tên là xâu kí tự 𝑊 có thứ tự từ điển lớn nhất thỏa mãn: có thể nhận được 𝑊 từ cả 𝑆, 𝑇 sau khi xóa bớt trong mỗi xâu một số kí tự (có thể không xóa kí tự nào). Nghĩa là tên được chọn sẽ là dãy con chung có thứ tự từ điển lớn nhất của 𝑆, 𝑇 .

Bạn được nhờ lập trình tìm ra tên cho loại nấm mới.

Dữ liệu vào:

  • Dòng đầu chứa xâu S ;
  • Dòng hai chứa xâu T . Hai xâu 𝑆, 𝑇 khác rỗng, chỉ gồm các chữ cái latin in thường, độ dài mỗi xâu không vượt quá 100000 .

Dữ liệu ra:

  • Một dòng duy nhất chứa xâu 𝑊 là tên được chọn, nếu không thể chọn tên thì dòng này để trống.

Ví dụ:

Dữ liệu vào:
superbom
sieunhancuoi
Dữ liệu ra:
uo