LCS nhỏ nhất từ điển

Bối cảnh và bài toán

Ngoài độ dài tối đa, hệ thống yêu cầu kết quả ổn định theo thứ tự từ điển.

Yêu cầu

Trong tất cả LCS của s và t, in LCS nhỏ nhất theo thứ tự từ điển. Dòng đầu in độ dài, dòng sau in chuỗi.

Input

Hai dòng s, t.

Output

Độ dài rồi chuỗi LCS nhỏ nhất từ điển.

Ràng buộc

• 1 <= |s|,|t| <= 200
• Chuỗi chỉ gồm a..f.

Chấm điểm

Ví dụ 1

Input

abcbdab
bdcaba

Output

4
bcab

Giải thích. Ví dụ nhỏ giúp kiểm tra cách mô hình hóa trạng thái và kết quả cuối; khi tự giải, cần suy luận từ ràng buộc thay vì suy đoán từ sample.

Ví dụ 2

Input

zyxabc
abczyx

Output

3
abc

Giải thích. Hãy đối chiếu với edge case: trạng thái đầu, trạng thái không đạt được, tie hoặc biên chỉ số tùy bài.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.