Truy vết LCS chuẩn hóa

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

Hệ thống cần một kết quả LCS tái lập được để so sánh log giữa nhiều lần chạy. Vì LCS có thể không duy nhất, quy tắc truy vết được chuẩn hóa.

Yêu cầu

In độ dài LCS và chuỗi nhận được khi truy vết từ (n,m): nếu hai ký tự cuối bằng nhau và thuộc một bước tăng LCS thì lấy ký tự đó; nếu không, khi hai hướng có cùng độ dài thì ưu tiên giảm chỉ số của s.

Input

Hai dòng s, t.

Output

Dòng 1 độ dài; dòng 2 chuỗi LCS chuẩn hóa.

Ràng buộc

• 1 <= |s|,|t| <= 1000
• Chuỗi gồm chữ cái thường.

Chấm điểm

Ví dụ 1

Input

abcbdab
bdcaba

Output

4
bcba

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

aaaa
aa

Output

2
aa

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.